Ahh..crap. My HP 5110 AIO showed right up and printed just fine. It used an All In One 2.7.2 Driver. Let me see if I can find it and you may be able to print using that driver.
Did you install the HP Printer drivers when you installed OS X? You can tell by going double clicking on your hard drive, then double click on Library, then find a folder called Printers and double click on that. If there is a folder called HP, then HP drivers were installed by default. I think Apple installs everything by default on a new Mac so if you've never reinstalled the OS, then all printer drivers should be pre-installed.
Also, I installed the HP Printer drivers for my HP AIO. It didn't find my printer either in the HP Setup Assistant, but it did in the OS X Printer Setup Assistant just to let you know. Just don't go through the HP Setup Assistant. It won't help you any.
Look at and see if you already have an AIO folder inside the HP Folder. If you didn't uninstall the HP software, then there should be an aio folder present. To look follow these steps:
1. Double Click on your Hard Drive
2. Find a folder called Library and double click on that
3. Find a folder called Printers and double click that
4. Double Click on hp (if present) If not present, stop right here!
5. See if there is a folder called aio (all-in-one). If there is, proceed to step 6, if there isn't, stop right here.
6. Go back to the OS X Printer Setup Assistant (Printers & Faxes System Preference) and click back on the + to add a printer
7. Let it discover your printer again and click ONCE on it to select it.
8. If it doesn't detect a driver, which it probably won't, keep going through these steps below
9. Click on the pull down menu that says Printer Using:
10. Select Other
11. Navigate to: yourHD/library/printers/hp/aio/hp_aio_plugin (something like that)
12. Click Open and see if shows a valid driver. If that pull down menu is grayed out, then it didn't pick up the driver.
Let me know if you don't understand something and I'll further explain any questions/problems you have. If it continues to be grayed out then you're pretty much SOL to print directly through the AirPort. If it comes to this...I'll help you with getting it to print using USB printer sharing on the Mac or through the PC.