Sender Policy Framework / SPF
A sender policy framework is a way to sign mail to authenticate the sender domain, a bit like DKIM / ADSP. DNS records are added to the zone file in order to achieve this.
An easy way to implement this is to add the following to your DNS record:
TXT "v=spf1 mx -all"
Best practice is to also publish it in this form in DNS
SPF "v=spf1 mx -all"
(they then have to be identical), but not being able to publish the SPF record is not a problem.
You always put the -all at the end of the record, as that's where the check stops processing and it tells the checker no more conditions will be met. You can replace the -all with ~all which will tell the system it's a soft fail, ie. other IPs are possible, but suspicious.
You do have to make sure that the DNS record has a valid MX record and that the url in the MX also has a valid A record in this case :)
If you are sending mail from another provider (eg integrated with Google apps) then you can include that as such
TXT "v=spf1 mx include:_spf.google.com include:other.provider.ext -all"