I never expected printer installation under linux to be so easy and hassle-free after a few unsuccessful attempts a few months back with an old Canon. This time it is an HP DeskJet 3820. HP has it's own linux printer support project:

HP Linux Inkjet Driver Project

After google turned up this page to me, my printer started to work within 10 minutes and 1 try. Voila :)