A brother printer hooked up to my AirPort Express base station was not recognized by the AirPort – so it seemed. The respective dialog in the AirPort Utility said: “USB Printer: None”.
I spent quite some time trying to find out what the problem was. It turned out that the dialog simply didn’t tell the truth. The “AirPort” dialog (left most in the menu) did indeed list the printer correctly:
After I found that bug setting up the printer both in OS X and Windows XP was a breeze. In OS X you go to System Preferences -> Printer / Fax -> + sign -> choose “Default” in the top connection-type menu. OS X will then try to locate the printer with Bonjour and populate the add-dialog with proper values. For Windows you need to install Bonjour from the CD that came with your AirPort Express base station.