You want processiong power, a Celeron based notebook won't cut it, neither will an Athlon XP based notebook. Centrino, Pentium-M, Pentium-D, systems are good, along with Athlon64, FX, X2 (if they have those in laptops now.)
Anything newer than a Radeon 9800PRO should also do good. But the newer the game, the newer the card you will need to run it at full blown settings. I've seen 6800GT's in a laptop, not sure if the 7 series has made it over yet though.
PC3200 or better, and preferably at least 1GB support. Really if you can find a lapotp that takes 2GB PC3200 you would be set, alot only allow 1GB however, which is fine too just not as much for games like BF2, F.E.A.R., etc.
Battery life is a big concern. You can buy bigger cell batteries later on if you need to though.
Screen, not to be overlooked. Make sure w/e you get has a decent screen. I personally like wide-screens, but try to avoid "mirror" looking screens that have ALOT of reflection. The smallest light in the room cast a HUGE glare on the screen, not good for gaming.
Of course other features are user dependant. I'd want integrated wireless support, DVD-player, larger HDD with decent RPM and cache size, and a solid design.