I've played games on two different laptops now, the first laptop I bought just to have a laptop and the second I bought with gaming in mind. Bottom line, I've found out, is that I wouldn't recommend any laptop for gaming.
I will tell you what I've discovered, though.
Don't bother with a high resolution (WXGA+) screen. We all know LCDs need to be run at their native resolution to look good, anything less is usually blurry/fuzzy. A high native resolution will kill you gaming performance.
Make the video card your priority. CPU and RAM aren't all that big of a deal (you'll want at least 1.8ghz and 1GB RAM), it's the video card that will bottleneck you in a laptop.
If you're planning on gaming on battery power, definently go with a Pentium M. I have a Pentium 4 in my laptop, and yes it does run hot (but that can be solved with other means). It sucks through the batteries in less than 2 hours no matter what I'm doing. It can barely make it through an average movie when watching DVDs on battery power. The Pentium M's are much more energy efficient.
If you're going to be using the AC power, well then I wouldn't worry about the processor all that much. A laptop cooling pad (
LapCool2 by Vantec is the best one I found in my research) can do wonders to keep the machine at reasonable temperatures. Before I got my cooling pad the base of the computer would be burning hot after a few hours of gaming. With the cooling pad, the base never gets more than slightly warm (if I allow proper airflow to get to the fans). Word of warning with the cooling pads: make sure you get the right fan flow. If the exhaust on your laptop is out the sides or back, you want a cooling pad that blows air up onto the base (fans blow up). If the exhaust on your laptop is out the bottom, you want a cooling pad that pulls air off the base (fans blow down).