An MX record is a DNS record which tells remote hosts the DNS names of the machines that accept e-mail for the domain. Each domain which you wish to receive e-mail for needs to have appropriate MX records. For your setup you probably want to have just a single MX record per domain, but you can set up multiple records with different priorities if you have backup mail servers.
This is a separate record type, so it won't show up in a "netcat mail.example.com". You have to explicitly request the MX record type. For example:
$ host -t mx gmail.com
gmail.com mail is handled by 20 alt2.gmail-smtp-in.l.google.com.
gmail.com mail is handled by 10 alt1.gmail-smtp-in.l.google.com.
gmail.com mail is handled by 40 alt4.gmail-smtp-in.l.google.com.
gmail.com mail is handled by 5 gmail-smtp-in.l.google.com.
gmail.com mail is handled by 30 alt3.gmail-smtp-in.l.google.com.
This shows several different mail server names that can be used to deliver mail to users at gmail.com, with different priorities (5 being the most preferred). Observe that the MX record is on the domain itself ("example.com") rather than on the mail host ("mail.example.com").
Note that if an MX record can't be found, the A record for the domain name will be used. So, if your mail server is on the same IP address as the other services, you could get by with just an A record. However, I'd recommend adding an MX record in any case, just to be clear and prevent changes to DNS from having unintended consequences.
DNS records, including MX records, are set up using whatever management interfaces your DNS hosting service provides. Often these are web interfaces, though if you are hosting your own DNS this would be in the zone files or database.
Note that backup mail servers are often abused by spammers, who try them to see if they are less strict about anti-spam measures, so make sure backup mail servers have similarly strict settings.
See Wikipedia's page on MX records for more detailed information