The Linux kernel mostly supports any printer that you can plug into a serial or parallel port, but there are things to look out for, and printers that you won't be able to use, even though they can (electrically speaking) communicate with Linux. Primary among these incompatible printers are those that rely on the "Windows Printing System". (They're often vaguely labelled "for Windows", or called "GDI" printers.) These printers do not work with Linux. They haven't any "smarts" at all, and rely on the computer CPU to do most of the work that has been traditionally done by the printer's CPU. Unfortunately, this work can only be done by the vendor-supplied drivers, which only run under Windows. So don't buy one to use with Linux. (Note that if you already have one, there are roundabout ways to get Linux to print to one, but they're rather awkward and I've never tried it myself. See Section 12 of this document for more discussion of Windows-only printers.)
As for what printers do work with Linux, the best choice is to buy a printer with native PostScript support. Nearly all Unix software that produces printable output produces it in PostScript, so obviously it'd be nice to get a printer that supports PostScript directly. Unfortunately, PostScript support is scarce outside the laser printer domain, and is sometimes a costly add-on.
Failing the (larger) budget necessary to buy a PostScript printer, you can use any printer supported by Ghostscript, the free PostScript interpreter used in lieu of actual printer PostScript support. The Ghostscript Home Page has a list of supported printers and information on the status of new and experimental drivers. Please help improve the Ghostscript printer support page by reporting your successes and failures as it asks.
Adobe now has a new printer language called "PrintGear". I think it's a greatly simplified binary format language with some PostScript heritage but no PostScript compatibility. And I haven't heard of Ghostscript supporting it. But some PrintGear printers seem to support another language like PCL, and these printers will work with Linux.
This section is and will always be incomplete. But whatever information I do put here should always be correct, so here goes:
One report suggests that the Canon works much better in Epson LQ mode (as set by a dip switch). Apparently output was intermittent or wrong in Canon mode. OTOH, there is much explicit Canon support in Ghostscript, so this might have been a fluke.
Lexmark (once part of IBM, I think) makes many printers; many of them, however, are Windows-only printers: