I extensively researched the companies that will sell laptops with no-OS or Linux preinstalled. This information is distressingly difficult to find, so I present a list below. I encourage you all to vote with your dollar and do not send a single penny to the monopoly in Redmond. If you want a linux laptop, pay for a linux laptop or there will be nobody selling them. The "Windows refund" efforts have largely failed, so it's best not to send any money to Redmond in the first place.
There are two kinds of companies with respect to manufacturing laptops. Original Design Manufacturers (ODM's) actually manufacture the hardware, which they then sell to Original Equipment Manufacturers (OEM's) that then install a CPU, RAM, hard drive, and software. Some major ODM's are Asus, Clevo, Compal, FIC, Mitac, Quanta, Uniwill, and Wistron. Major OEM's are the ones you're probably familiar with: Compaq, Dell, Gateway, HP, IBM, Sony, and Toshiba. TuxMobil has a more complete table of some of these manufacturing relationships.
There are vendors out there that will sell you a branded OEM laptop with linux on it. Since none of the major OEM's sell linux preinstalled on laptops at this time, this means that any vendor claiming to sell an OEM laptop with linux on it paid for windows and removed it (now with the exception of Dell, see below). I think this is a deceptive practice so I do not list such vendors below. Vote with your dollar folks. Also if you are interested in a laptop from a major OEM, call them up and ask for linux. If we make enough noise, eventually even the big guys will sell linux too (IBM and Dell tried in the past but sales were low).
You should realize that most of these companies below purchase the hardware from these ODM's just like the big name OEM's. So when you find some no-name laptop, it is usually equivalent to some branded laptop that never touched the hands of one of the major OEM's. (And figuring out exactly *which* brand-name laptop it is equivalent to can be extremely difficult) Mine for instance goes by the names Compal CL00, ChemBook 3020, and Toshiba 3000-S304. Some of the below claim to manufacture their own notebooks, but what this means is that they buy them from an ODM and put in a hard drive/CPU/RAM, which is why you will find identical looking cases at several of these vendors.
Lastly I encourage people to post their experiences to Reseller Ratings or a similar company/product ranking site, so that we can all learn from your experience, and vendors are pressured economically into being nice to their customers.
Update: TuxMobil now has a more complete list than me (and so does LXer) which you should look at. (But beware many vendors in their lists will pay for windows and remove it -- the vendors below definitely do not.)
Most (all?) of the vendors that preinstall linux offer some form of software and hardware support. As always, check the individual vendor's warranty and support policies to see if they meet your needs before buying.
Purchasing a no-OS laptop can be somewhat treacherous. Since there is no software, there is no reliable way for the vendor to identify hardware problems. Some tech support requests are hardware problems, others are software problems, and others are user error. When some customers use Debian, others Red Hat, others XBSD, you can see tracking down problems would be extremely difficult. If you purchase a no-os laptop, you should be capable of installing your favorite OS and performing basic tech support for yourself.