Sender Policy Framework (SPF) is a mechanism used to help prevent spam. Basically, an SPF record is a record in your organization’s DNS server that announces to the world the IP adddreses from which you normally send out email.
Hence, if another server receives email supposedly from your SMTP domain, the server first checks if the session was established from one of the IP addresses you listed in your SPF record. If not, the message is mostly likely spam.
So how do you define an SPF record. This can get a little tricky. But Microsoft has a wizard that lets you create an SPF record easily. Check it out:
Update 7/22/2016: The above link is dead. Consider this wizard instead: http://www.spfwizard.net/
Special thanks to Debra Peterson from WhoIsHostingThis for spotting the broken link.