If you're going to be mobile with the laptop - surprisingly enough, many who buy portables don't use them for that purpose - check out the battery life. The longer the better.
Second, how much heat the laptop puts out is important no matter how you use it. A hot porty is no fun on your lap and some machines that I've tried get uncomfortably hot by around the area where you rest your hands when typing. A related issue here is how the heat is dissipated... some laptops have incredibly noisy little fans.
The above factors are related to your choice of CPU but I would give them priority over simple processor performance metrics.
Ditto to what Juha said, sometimes slower processor yield better user experience and longer battery life than what gruntier processor can do.
I have an UMPC (eo i7210) which has Pentium M ULV 1.2GHz with 1GB ram, and it is the highest processor rate than what is available out there today for its UMPC class. Yet it feels very warm-hot when holding it, no matter if A/C or battery operated.