I have had absolutely no problems with Linux and HP or Toshiba laptops - Linux has drivers for almost everything so I think you have to be a little unlucky to get a non-compatible system.
Despite all that, I do look carefully at the documentation for the particular laptop I want and check that Linux has drivers for all the chips (except perhaps for the software modem) before I buy a machine.
Vendors such as RedHat maintain compatibility lists. You can also look at www.tuxmobil.org
to see if anyone has posted a review of a particular laptop you are interested in.
Most (if not all) Intel support chips work very well; Intel has put in a big effort in the past few years. Of course, all AMD support chips also work very well. Some VIA chips are reported to be strange (so be careful with VIA chips - but having said that, I've used embedded microcomputers with VIA chipsets and had no problems). Some NVidia chipsets are strange and I'm not sure if they are all 100% supported by Linux yet. The NVidia graphics chips definitely are not 100% supported by Linux (but I use NVidia + the proprietary drivers on my desktop system).