1. Check for the amount of memory. Too many cheap laptops have far too little. 512MB is an absolute minimum, with 1GB preferred.
2. If you're into games, take a good look at the GPU. The amount of RAM in the GPU is almost totally meaningless, it's the GPU itself that is important. There's too many GPU's out there to list a simple summary here, but a good rule of thumb is that for games, stay away from integrated video.
3. The CPU determines a lot about the heat a laptop will put out. As far as Intel goes, the Pentium 4 is crappy, the Pentium 3 is halfway-decent, and the Pentium-M and Core processors are good. As far as AMD goes, I think their Turion line is pretty good, but I'm not certain about their older lines. Transmeta's Crusoe processors, while a bit slow, are excellent for battery life.
4. Old laptops will often come with old batteries. This means that you can't expect a refurbished laptop to have good battery life, unless you purchase a new battery, which can be expensive. If battery life is important to you, you're usually better-off buying new.
5. The size of the laptop is an important consideration. No one size is best for everybody: larger laptops have larger screens and easier-to-use keyboards, but are more cumbersome to carry around. Smaller laptops often have longer battery life and are much more convenient for carrying around.
Anyway, those are just some basic considerations.