My Thinkpad R60 was stolen a couple weeks ago, and I probably will not be seeing that again. I'm in the market for a new laptop, and I want to see how much I'd have to pay for one with a dedicated GPU that can handle this game. Suggest away!
I would also make sure that the laptop has a either a ATI or nVida card. I have a Sony Viao laptop with an Intel Graphics Media Accelerator 4300HD that has issues with games if I have the graphics turned up high. STO does run on it with out any problems but I have to keep the graphic settings set to low because I have had issues with a couple other games with this card.
I've played games on laptops for years, and I currently play STO on a laptop.
First you want a Dual Core CPU that's at least 2 Gigs. You'll want 4 Gigs of RAM, preferably DDR3. For a graphics card you'll want an NVIDIA GeForce GT 240M at an absolute minimum. Don't bother with ATI video cards, they just have too many problems with STO to be worth it.
I've also noticed that a lot of otherwise great laptops are being sold at low prices because they have Vista. Whatever you do, do not get a laptop with Vista. Vista is worse than just junk, it's a nightmare. It will actually decrease the performance your hardware. Get Windows 7, preferably the 64 bit version.
If you PM me how much you are looking to spend, how big a screen you want, how much battery when not playing games, etc. I will go find some laptops out there for you that will play STO for a good price.
Peregrine is absolutely right about having a machine with an NVidia card in it. ATI puts out a decent product, but getting the two cards to do the same thing have enough coding variations to where one will come up short because the game was programmed to work on the other. ATI has always come up short in this respect and if it is not a coding issue, ATI's Catalyst Control Center is a big enough resource hog to where it causes its own slew of problems. Ask anyone who has tried to play Titan Quest on a machine with an ATI card and you will understand. I run STO on an Asus G60 JX with an Nvidia GeForce GTS 360M and the game runs just fine.