If you haven't got this working yet maybe this will help. First - it is one of the more difficult parts of Nagios to configure, don't feel badly. I spent several days trying to get this to work. Granted I was a complete noob to Linux and Nagios at the time, but it still wasn't easy.
You do have to have a local email server installed. You may be able to use the script sent by Tim but I have never seen it. Might be a great fix, don't know. But if you install Postfix you will be part way there. You must then set Postfix to relay through your SMTP server, or set it up to be an SMTP server on your network. Assuming you have an Exchange server or something similar, you need to configure the Exchange server to accept relays from the Nagios server. You typically do this in the SMTP properties of the Exchange System Manager for your Exchange Server. Once that is done you need to edit the path for the mail/bin directory in your "Notify Host By Email command in Nagios. Here is my command line from that config:
/usr/bin/printf "%b" "***** NagiosServerName***\n\nNotification Type: $NOTIFICATIONTYPE$\nHost: $HOSTNAME$\nState: $HOSTSTATE$\nAddress: $HOSTADDRESS$\nInfo: $HOSTOUTPUT$\n\nDate/Time: $LONGDATETIME$\n" | mail -s " $NOTIFICATIONTYPE$ -PROD Host Alert: $HOSTNAME$ is $HOSTSTATE$ **" $CONTACTEMAIL$
The key is the section with the pipe and maybe the first part of the command with the path. Its been a while, but the canned command that comes with Nagios isn't correct for where Postfix installs its mail buckets. All depends on what Linux variety you are using and what version of Postfix. Mine is Debian Lenny and the latest Postfix. IIRC I also installed MailX and that made a difference but its been a long time. The real key was editing the command file path to be sure you point Nagios to the correct mail executable.
I hope this helps. Just keep screwing with it. If you know the command line SNMTP commands it will help you debug. You can telnet to any mail server on port 25 and send mail manually. The feedback this gives will tell you a lot of good stuff. Look up SMPT CLI commands and you will find a lot of sites on them.