I'd advise cruising through
Newegg and like sites. You might find some notebooks that aren't really "name brand", per se, but for the price of an HP or Dell machine you can get an ASUS or Acer notebook with better hardware. The internal parts of every single computer on the market are invariably made in the same places by the same companies, the only real differences between brands are going to come down to customer service and, more importantly, driver support. You can get a pretty decent gaming notebook for around $700-900, if you look around. Generally the really hardcore gaming notebooks are going to cost you a lot more than that, and unlike with desktops the differences in rendering power between a $1,500 and a $2,000 machine aren't going to be that drastic. But for under a grand you can get a machine that will play most recent games very fast at medium settings at not-too-small resolutions. If you've got an extra hundred or two to invest in a no-questions-asked warranty, all the better.
I got an
$800 notebook last month and it runs Mass Effect and Neverwinter Nights 2 at very high frame rates with little compromise as far as graphics settings go. Fallout 3 has some hiccups but it's otherwise golden. As far as cooling goes, well... My lappy runs pretty warm most days, and the vent is on the right side, and I'm right handed so I get sweaty hands when using a mouse, but if you've got still more money to burn ($40-100) you can get a base for your notebook that will cool it while running off a USB slot. Those are pretty nice.
So obviously, you'll want a computer that comes with something better than a standard GFX chipset (avoid Intel GMA chipsets or whatever. Gravitate towards ATI or Nvidia chipsets, the higher the product number the better, generally) with at least 512 MB of DDR2 VRAM. If you can get 1024 MB, great (this is what I got). If you can get DDR3 VRAM, even better. You'll want a 2.0 Ghz dual core processor at least. If you can find a better processor, great, but I don't think that you will, as even the 2.12 Ghz's get up beyond a grand most days.
If you're going to leave Vista on the system, make sure it's got at least 3 GB of RAM. If you'd rather not deal with Vista, see if the vendor sells XP drivers for the notebook on a disc. You'll still need an XP install disc. Or you could Linux it. With WINE it's not as bad of an OS for gaming as it used to be.
Other thoughts, read customer reviews (Newegg's good for this) and try to pick out consensus on problems and strengths. If the computer has flimsy keys or badly placed vents or impractical LEDs or shoddy disc drives, people will notice and complain. Also, don't be afraid to wait it out until you're absolutely sure you need to buy. With laptops, just like with desktop processors and video cards, there's a lot of competition, and as such prices are always going down. Buying something only to see its price drop by $100 or $150 a week later is a common occurrence. But keep in mind that one of the ways they keep prices low is by limiting supply, so if you think something you want is going to sell out quick, jump on it.
Hope that helps.