Second, you should enable SMB sharing. I think this is called Windows Sharing in the Sharing preferences pane. I am not sure how my PowerBook finds the remote modem. It could be the SMB service, or the Rendezvous, but I am not sure about that. Now we come to the fun part.
Open the print dialog (File: Print or Command-P) and click the Fax button. In the following dialog, you can enter the fax numbers, dial prefix etc., as usual. In the Modem drop-down menu, you will see a Shared modem entry. I see the remote modem there and can select it for faxing. The rest is the same as if you are using a direct line.
[robg adds: A friend (thanks Jacco!) pointed out that this capability comes from efax -- it's not reliant on any of OS X's sharing services, so you can ignore the bit above about SMB. (I tested it with SMB, printer, and personal sharing all disabled, and it still worked fine.) I also couldn't see my newly-customized fax machine name from the PowerBook, even after restarting the PowerBook and doing a sudo kill -HUP [efax_PID] on the desktop machine ... I'm not sure what step I might be missing to see the customized name...]

