http://www.cce.com/efax/ would be a good start, but that's only going to work with a faxmodem. Any RS-232 faxmodem and USB-RS232 or BT-RS232 should do nicely.

A cellphone may also work, but I've heard that a lot of providers block that (data and fax calls) unless you pay extra. In theory, it should be as simple as setting up the RFCOMM device and using efax with it, I think (Assuming your handset uses AT commands). (For which RFCOMM to use, I'd go with gnokii, gnokii-gconf, and phonelink, which you probably want anyway; when you've got that working, you know the settings...)

If you think that sounds good, I can give compiling it a shot...