You can print to a fax machine with, or without, a modem.
There are a number of fax programs out there that will let you fax and receive documents. One of the most powerful is Sam Leffler's HylaFAX. It supports all sorts of things from multiple modems to broadcasting.
SuSE ships a Java HylaFax client which allegedly works on any Java platform (including Windows and GNU/Linux). There are also non-Java fax clients for most platforms; GNU/Linux can almost certainly handle your network faxing needs.
Also available, and a better choice for smaller installations, is efax, a simple program which sends and receives faxes. The getty program mgetty can receive faxes using efax (and do voicemail or interactive logins).
There is an experimental service offered that lets you send an email message containing something you'd like printed such that it will appear on a fax machine elsewhere. Nice formats like postscript are supported, so even though global coverage is spotty, this can still be a very useful service. For more information on printing via the remote printing service, see the Remote Printing WWW Site.
A number of companies operate web-based faxing services. EFax, in particular, offers free inbound faxes (to your own dedicated fax number, no less) via email, and fax transmission for a fee. Other companies offer similar services.