You need to install the Bonjour Printer Wizard software on your Windows machine so it can find the printer (should be downloadable from Apple - it came on my Airport Extreme install disk).
Additionally, I had to attach the printer to my Windows machine directly to get the drivers installed (HP printer drivers wouldn't install if it didn't see the printer..typical Windows BS). Then I reattached it to the Airport and it worked.