I would go for an Intel Core 2 Duo based laptop, they are the fastest mobile processors around and have the longest battery life. Look for the 'Centrino' logo, although if possible avoid the older Core Duo processors (which can also be labelled as 'Centrino' as they are older and inferior.) In terms of performance, AMD cannot match Intel and they are not much cheaper for that.
Look for a laptop with 2gb ram and with regards to the graphics card, yes you do need a dedicated one for gaming. Ideally try and go for a Nvidia Goforce 8600 series or ATI Mobility Radeon HD2600 series, there are several variations of these, hence me putting series, but they will all perform well for a laptop graphics card. Failing that, the Nvidia Goforce 8400 series or ATI Mobility Radeon HD2400 series provide adequate performance, although they may well struggle with even fairly modern games. You could also consider the older Nvidia 7600 series or ATI X1600/X1700 series, but keep in mind these cards are older and do not support DirectX 10 like the the aforementioned cards.
wclick here and click here are good, well respected suppliers. My favourite brand of laptop is Asus (they build many of the Sony Vaio lineup and are thus very good quality) as they look good and, unusually, have a 2 year warranty. Toshiba is another very good make.