The cheapest solutions would be:
- Buying a dedicated print server (or a wired/wireless router with one)
- Buying a network connector (e.g. HP JetDirect)
There a bunch of print servers you can buy for $40-$100, depending on brand, model, and features. A standard parallel-port print server with a 10BaseT interface is the cheapest, at about $40. There're USB ones for $50. The nice thing with dedicated print servers is that they work with most platforms, including Windows, Mac OS (9/X), Unix/Linux, etc. Most dedicated print servers use the tried-and-tested Line Printer Daemon (LPD) protocol, the old Unix standard for network printing.
The second alternative would be to buy a network connection device. HP sells their JetDirect line of expansion peripherals that makes their printers networkable. Similar to a print server, it gives the printer an ethernet connection, so you can print directly to it. The downside to the JetDirect device is, aside from its being model-specific, and usability with HP-only devices, the driver has to be specifically instructed for JetDirect printing. I'm not sure whether all HP printers have a JetDirect expansion option.