It's ridiculously simple:

  1. Connect USB cable
  2. sudo apt-get install hplip-gui
  3. hp-wificonfig
  4. Select network, insert password if necessary
  5. Disconnect USB cable

At this point you can connect to your printer via wireless. You may need to set it up separately using hp-setup or System → Administration → Printing. In the latter you can rename or remove the USB connection to avoid confusion with the wireless configuration.