Let's say that the mail server at mail.example.com sends mail to someaddress@gmail.com and the from address is "junkemail@handynerds.com"
Gmail will look up the SPF record at handynerds to get a list of all the mail servers that are authorized to send mail using a from address of handynerds.com Because example.com is not one of them, it will refuse (or at least suspect) the mail.
If I send mail from my handynerds.com mail server, it all works just great because my mail server is allowed to send mail from that domain.
How do you get an SPF record? Well I have some more information at a page that talks about ISP black lists and SPF records.
This actually is a discussion about me setting up a new e-commerce site with its own dedicated mail server and the issues that I had to go through. Hopefully helping others do the same. It includes a discussion about SPF records.
In short, it requires you to add a record to your DNS for your domain. If you are hosted, you most likely need to ask your service provider for help. If you are using DNS at godaddy, it can be done through TXT records. If you want to run your own DNS, I highly recommend editdns.net. They are free, and have great customer service.
Running your own DNS is not for the faint hearted though. I run my own because I am familiar with it, and because I am also running IPv6 so I need specialized records. It is really easy to mess something up and take yourself off the grid (so to speak) so make sure you know what you are doing.
Good luck.
--Brett Thorson http://www.Best4Men.com/ The best men's grooming products, all in one place.