What are SPF records, and how do I configure them?

SPF records detail which servers are allowed to send mail for your domain.

Questions 1-3 really summarise the whole point of SPF: You're supposed to be listing the addresses of all the servers that are authorised to send mail coming from your domain.
If you don't have an exhaustive list at this time, it's generally not a good idea to set up an SPF record. Also a domain can only have one SPF record, so you'll need to combine all the information into a single record.

The individual questions really just help break the list down for you.

1. asks you for other domains whose mail servers may relay mail from you; if you have eg a secondary MX server at mail-relay.example.org, and that is the main mail server (MX record) for the domain example.org, then you should enter mx:example.org. Your SPF record should include your own domain's MX record under nearly all circumstances (mx).
2. asks you for your ip netblocks. If you have colocated servers at 1.2.3.0/28, and your office address space is 6.7.8.0/22, enter ip4:1.2.3.0/28 ip4:6.7.8.0/22. IPv6 space should be added as eg ip6:2a01:9900:0:4::/64.
3. if (eg) you also have a machine off in someone else's office that has to be allowed to send mail from your domain, enter that as well, with eg a:mail.remote.example.com.

Your mobile phone users are problematic. If they send email by connecting to your mail server using eg SMTP AUTH, and sending through that server, then you've dealt with them by listing the mail server's address in (2). If they send email by just connecting to whatever mail server the 3G/HSDPA provider's offering, then you can't do SPF meaningfully until you have rearchitected your email infrastructure so that you do control every point from which email purporting to be from you hits the internet.

Question 4 is a bit different, and asks what recipients should do with email that claims to be from your domain that doesn't come from one of the systems listed above. There are several legal responses, but the only interesting ones are ~all (soft fail) and -all (hard fail). ?all (no answer) is as useless as ~all (qv), and +all is an abomination.

~all is the simple choice; it tells people that you've listed a bunch of systems who are authorized to send mail from you, but that you're not committing to that list being exhaustive, so mail from your domain coming from other systems might still be legal. I urge you not to do that. Not only does it make SPF completely pointless, but some mail admins on SF deliberately configure their SPF receivers to treat ~all as the badge of a spammer. If you're not going to do -all, don't bother with SPF at all.

-all is the useful choice; it tells people that you've listed the systems that are allowed to send email from you, and that no other system is authorized to do so, so they are OK to reject emails from systems not listed in your SPF record. This is the point of SPF, but you have to be sure that you have listed all the hosts that are authorized to originate or relay mail from you before you activate it.

Google is known to advise that

Publishing an SPF record that uses -all instead of ~all may result in delivery problems.

well, yes, it may; that is the whole point of SPF. We cannot know for sure why google gives this advice, but I strongly suspect that it's to prevent sysadmins who don't know exactly whence their email originates from causing themselves delivery problems. If you don't know where all your email comes from, don't use SPF. If you're going use SPF, list all the places it comes from, and tell the world you're confident in that list, with -all.

Note that none of this is binding on a recipient's server; the fact that you advertise an SPF record in no way obliges anyone else to honour it. It is up to the admins of any given mail server what email they choose to accept or reject. What I think SPF does do is allow you to disclaim any further responsibility for email that claimed to be from your domain, but wasn't. Any mail admin coming to you complaining that your domain is sending them spam when they haven't bothered to check the SPF record you advertise that would have told them that the email should be rejected can fairly be sent away with a flea in their ear.

Since this answer has been canonicalised, I'd better say a few words about include and redirect. The latter is simpler; if your SPF record, say for example.com, says redirect=example.org, then example.org's SPF record replaces your own. example.org is also substituted for your domain in those look-ups (eg, if example.org's record includes the mx mechanism, the MX lookup should be done on example.org, not on your own domain).

include is widely misunderstood, and as the standard's authors note "the name 'include' was poorly chosen". If your SPF record includes example.org's record, then example.org's record should be examined by a recipient to see if it gives any reason (including +all) to accept your email. If it does, your mail should pass. If it doesn't, the recipient should continue to process your SPF record until landing on your all mechanism. Thus, -all, or indeed any other use of all except +all, in an included record, has no effect on the result of processing.

For more information on SPF records http://www.openspf.org is an excellent resource.

Please don't take this the wrong way, but if you get an SPF record wrong, you can stop a significant fraction of the internet from receiving email from you until you fix it. Your questions suggest you might not be completely au fait with what you're doing, and if that's the case, then you might want to consider getting professional assistance before you do something that stops you sending email to an awful lot of people.

Edit: thank you for your kind words, they're much appreciated.

SPF is primarily a technique to prevent joe-jobbing, but some people seem to have started to use it to try to detect spam. Some of those may indeed attach a negative value to your having no SPF record at all, or an overbroad record (eg a:3.4.5.6/2 a:77.5.6.7/2 a:133.56.67.78/2 a:203.54.32.1/2, which rather sneakily equates to +all), but that's up to them and there's not much you can do about it.

I personally think SPF is a good thing, and you should advertise a record if your current mail structure permits it, but it's very difficult to give an authoritative answer, valid for the entire internet, about how people are using a DNS record designed for a specific purpose, when they decide to use it for a different purpose. All I can say with certainty is that if you do advertise an SPF record with a policy of -all, and you get it wrong, a lot of people will never see your mail.

Edit 2: deleted pursuant to comments, and to keep the answer up-to-date.

What's important for your setup is the configuration of the server which finally sends the email to the internet. You say that you send emails via SMTP. So in terms of IP address what matters is the configuration of your SMTP server ( question 2 )

If you are using a third-party, such as gmail, to send your emails, you have to include their spf records like this: include:_spf.google.com ( the ajax wizard does not seem to know about this ).

For the "How Stringent", leave the "soft fail" ( ~all ) if you're unsure, but else "reject" ( -all ) is the way to go once your configuration is clean.