I thought I could plug in any printer there and print over the air to the airport express's usb printer...
Not all printers are compatible with the USB port on the AirPort Express....and....AirPrint is a completely separate matter. This is a separate Apple feature that allows an iPad or iPhone to print to an AirPrint compatible printer using wireless.
The printer has to connect to the network using wireless for AirPrint to work....not USB. You might be able to use a separate App like Printopia to allow the iPad to print when the printer is connected to the USB port.
There is a free trial for Printopia, so you will know if it will work before you buy.
Printopia - AirPrint to Any Printer - Print from iPad - Print from iPhone ...
But, first things first. You need to see if you can get printing to work normally first from your Mac....and then try Printopia to see if it will allow the iPad to print.
But the main problem is that it won't download any software... Even when I plug in the printer into my Macbook, it says "searching for software" and then "Cannot download software now, there is a network problem." But I'm clearly connected to the internet so...
Have you tried powering off the MacBook and the AirPort Express?
Have you contacted HP Support to ask them about whether they still support your printer....and whether there any new printer drivers that you could manually download and install?