I just jumped through these hoops myself today. What I had to do was update the firmware in the printer. Go to the HP site here:
and do this:
1. Download the firmware updater to your MAC (laptop, desktop, etc.). Could do this with a WinDoze machine as well, just in case you work both sides of the computer world.
2. Hook up the computer to the printer with a USB cable. From what I've read on various other threads here and other websites, the HP firmware utility doesn't work over a WiFi connection - I can't say this is true for sure, I just did it with a cable wanting to avoid problems.
3. Run the HP utility and install the firmware. It takes a minute or so to complete.
4. Turn off the printer and turn it back on.
5. Once done, you can disconnect the cable. You can check the printer firmware version through the Mac's printer utility for the HP - look at the "printer webpage" button on the utility screen. It will display the printer's info, amongst which will be the firmware revision. Make sure it matches the latest version (you just loaded).
6. I tried printing a doc. from my iPad2. It didn't work at first. So I powered it down, and back on and was able to print. Not sure why this was necessary, but it worked. Anyway, once you get to this point, you try to print a doc. it should show the printer in the device list.
This worked for me. I tried with iPhone 4 and iPad 2, with latest iOS 5 and both worked. One aggrivating thing, the iPad gives you no status after hitting the "print" button. I would hope that is something Apple will do something about in the future. Kinda nice to know if the status with some indicator, especially if the printer is upstairs and at the back of the house (uuugh).
It's possible to use free software (Virtualbox and Ubuntu) to fix the broken iOS 5 Airprint printing with non supported printers. Here's a fix that works on my imac, but should also work on even a windows pc.
My setup is a lion imac with 2 non-airprint supported usb printers attached, a belkin wifi router that provides network connectivity for my imac, ipad, and iphone.
Install ubuntu 11.10 in a virtualbox vm. Specify to use the "Bridged Adapter" with "en1: WiFi (AirPort)" for the network hardware. Make sure the imac's usb printers are setup with sharing. On ubuntu, select System Settings > Printers and add your imac's shared printers to the list. Then start ubuntu's firefox and set "localhost:631" in the address. On the administration tab, under the Server section, check "Share printers connected to this system" and hit Change Settings button to activate it. Go back to ubuntu's printer setup, and right click on each printer and check that the properties Policies tab does not have any messages about it being unshared. If so, then go back to firefox and make sure the Server sharing checkbox is enabled. It may help to reboot.
Fire up virtualbox to be able to use AirPort printing to your imac's usb printers, when you want to print from the iphone or ipad. This also works on iOS 5.
Only problem is error message from iphone to check the printer for errors, even though it actually prints ok.