What's CiviCRM's FQDN for mail?
SPF works by specifying what hosts can send email for a particular domain. Hence you should be thinking about adding your host to their SPF record (not 'their FQDN in our spf record').

If your client is sending email from addresses like info@client.org and that email originates from one of your hosts, for example host.provider.com, then  you will need to ensure that something like 'a:host.provider.com' appears on the SPF record for client.org.

If they don't have an SPF record already, you'll want to chat with them about how they are sending email before setting anything up to ensure that you correctly identify all the different hosts that send email for this domain in the SPF record.

Here is a good SPF resource for further reference: http://www.openspf.org/SPF_Record_Syntax.