I mostly haven't needed fax software, as my Australian designed MicroFax modem did the entire job, and doesn't really even need a computer connected most of the time.
Works independent of computer brand, and doesn't even need to be connected to a computer to work. Unfortunately, they are no longer available.
Here are a few fax programs I've heard mentioned, mostly for HP200LX or MS-Dos palmtops. Please note that I haven't tried them, as I haven't needed them, so don't ask me how (or even if) they work.
Ace-Fax, from Ace Technology, for HP palmtops. Occupies 190k, cost reported as US$29 on sale. They had a web site at www.web-server.ace-tech.com
BGFax by B J Guillot (firstname.lastname@example.org April 1996) requires only four files (bgfax.exe, makefax.exe, bgfax.fnt, bgfax.cnf) for sending faxes. You would need view.exe to view faxes on CGA displays. Available on http://www.blkbox.com/~bgfax/
Faxit! shareware for Psion, available at http://ourworld.compuserve.com/homepages/WalterWright/
Qfax, by Anthony Mai (HXM3@psuvm.psu.edu - April 1996) was a simple fax program for PCs, about 100k. Search for qfax on www.shareware.com or Simtel
SSFaxer, produced since 1992 by Simple Simon Software. Now on version 8. There is a TryWare version which includes sending, receiving, converting, viewing and printing. Try http://www.simplesimon.com