Short bio: Computer Scientist, FOSS supporter (read more)
Tux Machines (TM)-specific
For my money, I'd first look to see if the company is an official partner of its Linux distributor. If I'm going to buy a SUSE Linux-powered computer, for example, I'd rather get it from someone who's a Novell partner rather than someone whose only connection to Novell is that they downloaded a copy of openSUSE 10.1.
Next, I'd look for a company that's been in the Linux business for a while. I'd want to know that if I have a technical problem, the first thing that the tech support crew suggests when I call isn't going to be to reinstall Windows.
When going over exactly what system I want to buy, I'm a big believer in the theory that's there's no such thing as too much RAM. If my budget is tight, I'd rather get more RAM than a faster processor or bigger hard drive any day of the week. In all my years of beating on PCs in tests, I've always found that the single easiest way to get more performance is to add more memory.