It doesn't need to be a PCI modem, but I would prefer one because everything can be nicely tucked away than and it's less wiring. But if only oldskool external serial modems do the job I'll use that then.
Just to confirm, something like this one: http://www.usr-emea.com/products/p-dialup-product.asp?prod=hom-5631a&loc... will just work out of the box?
There are/were two products for unix faxing - mgetty and hylafax, so check out their hardware compatibility lists.