I have a 3 or 4 year old Sager NP2096. I bought it with Linux in mind while looking for pc's. Found mine at http://www.xoticpc.com
Anyway, what you want to look for is for two more specific bits--the wireless card and the video card. Myself, I like to look for Intel parts for the wireless chip, they seem to play nicely with Linux.
For the video card, go for a nVidia. As long as you don't buy the newest cards, they work well with Linux, and with dkms and one click installs for the driver in Mint, it's a piece of cake to set up.
After that, think about what you want to do with the PC.
Just email and surfing? Find a 2 - 2.2Ghz dual-core processor
Gaming? Find a 2.4 - 3.0Ghz dual-core
Hosting servers? Go for a quad-core.
These are just some things to look at.
Remember that if you want a large screen, or an external monitor, you'll need to look into getting a decent video card, or you could be looking at some lag if you're watching videos or playing games on the external.
And finally, if you have the hardware, see if you can boot up your favourite distro, see if the disc works, and if there are no hiccups, shouldn't have too many issues. Keep in mind, most problems in Linux can be resolved with a little help from the community, Google, and some command line.