It's not frequently that I dispense consumer advice, but on this occasion I will. I spent a great deal of time trying to determine which relatively new (and therefore purchaseable) printer with a scanner would work flawlessly on Ubuntu Linux (technically Kubuntu 9.10). I eventually settled on the HP Photosmart C6380 and I have not been disappointed.
I plugged the printer in, followed the setup instructions to install the print head and cartridges: approx 10 mins.
I then went into the tools menu and selected wireless. The device instantly found my WEP protected wireless network and prompted me to enter (somewhat laboriously) the hex key for the network. The only part of this that wasn't intuitive was that you must ensure, if using a hex key, that the letters are entered uppercase - it won't automatically convert it for you.
So, it was crunch time. HPLIP 3.9.2 (I believe) is automatically supplied with Ubuntu 9.10 and this claimed to support the device. I tentatively dropped to a shell prompt and ran:
sudo hp-setup
It came up with a dialog prompting me to find the printer. I was a little dismayed that it didn't automatically find it on the network (the inbuilt KDE printer setup *does*, but you need to do hp-setup for scanning). Anyway, I quickly logged in to my router, determined the IP address of the device (and set it to remain static) and whacked this into hp-setup. Tada! The device was found and the installer swiftly completed.
I then printed test pages, which was no problem. I opened XSane and it immediately found the scanner, again, with no problems. Then came a part that I was dreading. I'd read that some people couldn't get the photo tray to work correctly. This was not a problem for me at all. I simply selected the photo tray and photo paper and it all worked - the only thing I'd warn about is that it doesn't like non-HP photo paper it seems.
In short, this was a thoroughly excellent purchase that I would recommend to anybody looking for a printer for Linux. I hope it helps somebody. The printer is available at Amazon.
Disclaimer: I've put affiliated links to the product on Amazon in this post. Be assured that I wrote this review because I enjoyed the product and thought it would save somebody a great deal of research time, not because I'm trying to make money out of it. Feel free to buy elsewhere!