The HP support for remote USB printing has been poor, but there is an open-source printer driver for HP printers called hpijs which will allow your HP USB printer to work with AirPort/Time Capsule USB printing. I installed it a few OS X versions ago, and it works fine. I use the HP 3550 with a Time Capsule.
The installation is a little hairy, only because you have to follow instructions and install a bunch of separate items. But it really is pretty easy, just make a stiff drink, download each of the packages and press "install". But I promise it really works (you can google for other testimonials). The link to the hpijs drivers is:
http://www.linuxfoundation.org/collaborate/workgroups/openprinting/macosx/hpijs
PS - I don't remember if it is also necessary to install the OS X Developer Tools. Couldn't hurt. Also I haven't tried 10.6 yet.