What program do I use to check mail?

On Debian and derived distributions, you can use the apt-file command to search for a package containing a file. Install apt-file (apt-get install apt-file) and download its database (apt-file update, Ubuntu does it automatically if you're online). Then search for bin/mail:

apt-file -x search 'bin/mail$'

With the command-not-found package installed, if you type a command that doesn't exist but can be installed from the Ubuntu repositories, you get an informative message:

$ mail
The program 'mail' can be found in the following packages:
 * heirloom-mailx
 * mailutils
Try: sudo apt-get install <selected package>

If you're not after mail specifically, but after any program to read your local mail from the command line, there are much better alternatives. All mail user agents provide the mail-reader virtual package, so browse the list of packages that provide mail-reader and install one or more that looks good to you (and doesn't use a GUI, if it's for a server).

mutt 's motto is “All mail clients suck. This one just sucks less.”, and I tend to agree, but in the end it's a very personal choice.

Another program you can use is mutt. I prefer using mutt to mail - it just has a nicer interface in my opinion.

# apt-get install mutt

should work - but I use Fedora not Ubuntu so can't confirm this.

Just install mailutils which must contain mail:

# apt-get install mailutils

Read more about mail and GNU mailutils here