Mail and DNS

The following assumes you either have a DNS provider of some sort, or are running your own DNS server and can edit things accordingly. I highly recommend using a provider - it is free from most Domain registrars these days, and high-availability providers like DNS Made Easy, EasyDNS and Dyn are relatively inexpensive for what they provide you.

This is really more of a checklist than a proper guide, may want to flesh things out in the future.

A common complaint about most of this is that it does not actually prevent SPAM being sent. That is not now, and likely never will be the goal:

FCrDNS tells the recipient that the entity delivering the package is who they say they are.
SPF tells the recipient that the originating post office is who they say they are.
DKIM tells the recipient that the organization boxing the package is who they say they are.
DMARC tells the recipient that the name on the displayed sender line is who they say they are.

These things are meant to help prevent forgeries. Inasmuch that it says to the world that you are who you claim to be, it provides a measure of trust accordingly.

Choosing an outgoing mail hostname

Be mindful that blocking generic and dynamic-looking hostnames is a thing, and even recommended in the guides posted here. While you are only likely to intentionally trip up if you have a lot of mailing domains, you certainly do not want to leave your PTR <-> hostname mapping as whatever your host has defaulted for you. On top of getting hit by generic blocks, you need to control the top-level domain in question in order to even talk to some companies.

If you are part of a large organization that needs many outgoing mailers, please consider doing what everyone but Microsoft is doing and make sure something obvious like 'mx', 'mail', or 'smtp' appears in its own block.

FCrDNS

Set a domain's A record to an IP address, and ask your host or use your host's software to set a PTR record for that IP to point to that domain name.
Same thing with AAAA records and an IPv6 address, if you want to send mail over IPv6. Some hosts won't set IPv6 PTR records yet - if planning to mail over IPv6, you may wish to verify this with prospective hosts.
1. Google in particular prefers to talk over IPv6, most other mail providers prefer IPv4. In any case, you can use gmail to double-check that your IPv6 mail stack is working properly.
2. Some providers will not yet provide PTR records for IPv6 addresses. It's possible that we may see /64-level PTR records of some variety in the future.
Many mailing solutions will recommend that you segregate your mail depending on its purpose. I would recommend some caution before doing this with abandon - mailing providers judge you in large part based on the amount of mail you send that gets actively read. You want to build up a good reputation on your IP, and nothing builds that quite like a forum where members use notifications to navigate.
Be sure to avoid generic-looking domain names for your outgoing mail domain. If your domain looks like xx-yy.mydomain.com, my own regexp will block it as generic-looking, and this is not something I, nor most people, are willing to change for your sake.

SPF

Sender Policy Framework

I use both TXT and SPF records if available.

v=spf1 ip6:2001:db8::4 ip4:198.51.100.187 a mx a:example.com mx:example.com -all

For each singular mail domain (typically the second-level - @). Some SPF providers also check the mailserver itself, so if your mailing domain is mail.example.com, you may want to add this there as well.

I generally publish

v=spf1 -all

For www, wildcard, other records. You'll need one for each record specified. Also a good idea to do this for domains that should not be sending mail.

DKIM

Domainkeys Identified Mail

DKIM is set up as TXT records on subdomains of the domain that mail is coming from (in the Return-Path line, @example.com)

_adsp._domainkey "dkim=unknown"
- Only one of use.
whateveridentifier._domainkey
- v=DKIM1;p=giantstring==
- The key would be generated by your signing software, presumably. Note that you can fit an 1152-bit key into the TXT record. Better than nothing.

It is generally more sane to use one per outgoing mailer, if that, rather than one per domain. Makes it much easier to add new mailing domains. You may find yourself rotating through keys, especially as 1024-bit and 1152-bit keys become easy to crack.

DMARC

Domain-based Message Authentication, Reporting & Conformance

DMARC requires you to setup SPF and DKIM first. Then you setup another TXT record under your @fromhere.com domain(s) accordingly:

_dmarc "v=DMARC1;pct=100;p=quarantine;sp=reject;adkim=s;aspf=s;rua=mailto:abuse_rua@example.com"
- I set _ as my mailing delimiter and direct it into folders accordingly.

The rua reports are not terribly large, so I'm happy to take them. You do get quite a lot of them, though, so you may want to specify ri:604800 or something. ri:3600 in most cases ought to be a temporary thing.

You will want to look at the documentation for what this all means. The above describes a full solution.