Which mailx package should I install for Nagios?

You should be able to install any of them. I have bsd-mailx on my system, and I don't see any reason not to go with it.

It appears that this is the intended migration path.
Here's some of the apt-cache show mailx output:

Depends: bsd-mailx
Description: Transitional package for mailx rename
 This dummy package is provided to smooth the upgrade from mailx to
 bsd-mailx and can be safely removed afterwards.

Two additional things, though. The instruction set you're using is quite old at this point (as you've seen, some package names change over time). And it's also about installing from source.

I'm assuming that you do actually want to install from source, presumably for more control or to get a specific version installed.
But in case you weren't aware of this (or for others who are not), there are a number of pre-built pacakges in the repositories for nagios already.

Here's some slightly edited output from apt-cache search nagios :

nagios3-core - A host/service/network monitoring and management system core files
nagios3 - A host/service/network monitoring and management system
nagios3-cgi - cgi files for nagios3
nagios3-common - support files for nagios3
nagios3-dbg - debugging symbols and debug stuff for nagios3
nagios3-doc - documentation for nagios3
nagios-images - Collection of images and icons for the nagios system
nagios-nrpe-server - Nagios Remote Plugin Executor Server
nagios-plugins - Plugins for the nagios network monitoring and management system
nagios-plugins-basic - Plugins for the nagios network monitoring and management system
nagios-plugins-standard - Plugins for the nagios network monitoring and management system
[...]
djagios - A package to help configure nagios written in Django
libnagios-object-perl - module to parse and represent Nagios configuration as objects
libnagios-plugin-perl - family of perl modules to streamline writing Nagios
mailping - monitor email service availability and functioning
nagcon - console application interfacing to Nagios
nagios-nrpe-plugin - Nagios Remote Plugin Executor Plugin
nagios-plugins-extra - Plugins for the nagios network monitoring and manegement system.
nagios-snmp-plugins - SNMP Plugins for nagios
nagios-statd-client - Nagios client for monitoring remote system information
nagios-statd-server - Nagios server for monitoring remote system information
nagiosgrapher - Charting add-on for Nagios
nagstamon - Nagios status monitor which takes place in systray or on desktop
nagvis - Visualization addon for Nagios
ndoutils-nagios3-mysql - This provides the NDOUtils for Nagios with MySQL support
nsca - Nagios service monitor agent
pomamonitor - A simple host downtime alert for GNOME/KDE desktop

You likely already have a suitable program installed. Try the commands: mailx -s Test postmaster and mail -s Test postmaster. Exit the command by entering to ctrl-cs in a row. If either is found and doesn't fail when called as above, you should be ok. If one of them fails, you will need to verify that the command used is the one Nagios uses. You can change the command in your configuration if necessary.