Creating SPF / Sender ID records
It seems like a few ISPs out there are "demanding" that people get valid SPF records. I have not tested this, but a few admins have reported to me that unless their domains have SPF records, HoTMaiL is putting their mail in the Junk Mail folder.
SPF / Sender ID is not really an anti-spam technology. It is an anti-spoofing / anti-phishing technology. If your SPF records are correct, and someone checks them, then it means that any message that claims to be from one of your users is REALLY from one of your users.
Before you can create an SPF record, you need a record of EVERY public IP address that will be sending mail on your behalf. That includes managed providers, bulk-mail senders (if you have mailing lists that you outsource), and the public IP addresses from which every SMTP message in your organization originates. Once you have these, then you can create an SPF record.
Make sure your records are accurate. The only thing worse than no records at all is having an incorrect record!
Here are couple of resources you can use to learn more about these as well as wizards for creating the SPF records that you will need to put in to DNS.
SPF: A Sender Policy Framework To Prevent Email Forgery
Sender ID Framework SPF Records Wizard
The Port25 folks have a neat feature that will do a status check on your SPF records. Send an e-mail message to firstname.lastname@example.org and they will reply with a report of whether they find SPF records for you or not.