bring up man for ghostscript.
here is an example with efax, but any fax program should work. (sendfax requires a class 2.0 modem but most cheap modems still only support class 1 which efax supports)
save the pdf created with php as a file in /tmp (an example). then:
exec("/usr/bin/gs -sDEVICE=tiffg3 -dNOPAUSE -sOutputFile=tiffg3_file_name pdf_file_name
</dev/null");
exec("/usr/bin/efax -d/dev/$fax_device -x/var/lock/LCK..ttyS0 -iM0L0S11=50X3S7=120 -o1 -h"To: remote_user @ their_fax_number Page#%d Of %d" -tTremote_fax_number tiffg3_file_name");
converting to tiffg3 takes about 5 seconds and faxing takes about 90 seconds for most faxes per page (even if your modem is a 14.4 modem most are still 9600) so you may want to have the script to send the fax run in the background.