I would recommend a Samsung ML-2851ND. It works under many - perhaps all - Linux Distributions out of the box without the need to install any additional software. It's a small printer for the SOHO market, so that the toner is quite expensive (compared to big office printers), but compared to similar printers from HP or Brother, it's quite cheap.
The printer has Ethernet, so that you can print from any computer inside your LAN. It has a Duplexer, so that you can print on both sides of a page. And it is a compact printer, so that it doesn't clutter your room.
I'm using the printer with Ubuntu 10.10, 11.04 and 11.10 without problems. It is automatically detected by the printing utility. If you like to read more, you might visit my blog, unfortunately it's written in German, perhaps the Google Translater is goo enough for you.