The Short And Sweet Answer
The fast answer is, MX (Mail Exchanger) records are the information that other companies and people use to figure out where to send mail for a given domain.
Not So Short, but Still Sort of Sweet
Explaining what an MX record is difficult without explaining DNS.
Domain Name System
Domains (like pobox.com) are just names. They need to be associated with IP (Internet Protocol) addresses so their services are reachable. DNS is used to organize that information and make it public.
If IP addresses are your telephone number, then domains are your name.
DNS is organized like a tree, with "." at the root, with Top Level Domains (like .com, .net, .org, .edu, and others) below.
Like most network protocols, everything is a conversation:
When you go to www.pobox.com, your local DNS resolver first checks its cache of already resolved names. If it does not find a cached address, it asks either its immediate upstream (like your ISPs nameservers) or one of the twenty-some root DNS servers.
The roots will say "pobox.com? go talk to .com."
.com will say "pobox.com? That's registered by Domain Discover, go talk to one of their nameservers."
Domain Discover then says "pobox.com? Here's a list of their nameservers, go ask one of them."
And then your DNS resolver asks one of our nameservers (ns1.rightbox.com for example) for the address of www.pobox.com, and your web browser connects to that address and asks for www.pobox.com.
Types of Records
DNS has a variety of records associated with it. An in-depth explanation of them is outside the purview of this article (see wikipedia), but suffice to say you can have a single name and associate different services with it by using different types of records.
The A record for pobox.com, for instance, is different than the MX records for pobox.com. For instance (this information changes as we add new resources to the MX pool, so please don't consider the following canonical):
$ dnsip pobox.com
$ dnsip www.pobox.com
$ dnsmx pobox.com
As you can see above, you can also associate multiple names with an IP address. Just as you, your spouse, and your children, may all be listed under the same phone number.
The MX records tell anyone doing that type of lookup which IP address(es) to talk to for mail for the domain they're interested in.
MX records also have a concept of priority. Above you see the number 10 next to each of the names returned by the 'dnsmx' command. If you specified 5 for a given record, a Mail Transport Agent on the Internet would try that host first. Smaller numbers are have higher priority than larger ones.
This matters if you add MX records with different priorities, and run your own MX out in the world (as, perhaps, a backup just in case something ever goes Super Evil Bad with Pobox... of course, if something goes Super Evil Bad with Pobox, our Operations team will be on it Super Fast and fix it!)
When you register a new domain, the registrar adds it to the list of domains they are authoritative for with the roots. That means when someone asks about it, there is somewhere to ask.
So, when you set up a personal domain with Pobox, there are 2 things that can happen:
You set up the domain with us, or transfer it to us. We become your authoritative DNS provider, and just make it go.
You have the domain with someone else. You tell us you want to add the domain to your account. You tell them, hey, point my domains MX records at Pobox! We change our DNS records so that our computers know they should respond for you.