Basically you just tell your Mail Transport Agent (MTA) to "relay" to the Exchange server. Usually the Exchange administrator has to configure Exchange to allow such relaying. (It is not allowed by default to prevent spam.)
How to setup "relay" in the MTA depends on which one you're using. I use Sendmail since that's the one that comes with most UNIX/Linux OSes by default. Many prefer Postfix but if you're not receiving mail there seems little reason to use Postfix.
Some notes on Sendmail setup for relaying (first you have to let it relay to itself because by default it denies relay from local host [ip 127.0.0.1] to the public IP of the host.
Typically Sendmail configuration is in /etc/mail so if I mention a file it is likely there.
Prior to doing anything be sure you back up the directory to another location so you can revert back to where you started if it all goes wrong.
Stop sendmail if it is running (typically there is a sendmail init script to do this in /etc/rc.d/init.d.
First look at sendmail.mc and find line that says something like:
Add another line just like it that has your public IP in place of 127.0.0.1 e.g.
Next locate the line in sendmail.mc similar to:
dnl define(`SMART_HOST', `smtp.your.provider')dnl
Remove the "dnl" from start of line (dnl = do not load) and add your Exhange server in place of smtp.your.provider so it looks similar to:
Also while you're add it add other names the Linux server is known by to the access file.
Typically it looks something like:
You'd want to add your fully qaulified domain name (FQDN) and short name to the file. So if your FQDN were yourlinux.yourdomain you'd end up with:
Once you've finished edit of these files you'd run "make -C /etc/mail" (or whatever directory you found them in) to compile then. The sendmail.mc compile will end up in sendmail.cf and the access file will end up in access.db. Note that sendmail.cf does not have same format as sendmail.mc even though both are readable ascii type files. access.db is a binary hash of the access file.
You'd then want to restart sendmail.
Once you've done all that you should just set notifications in Nagios to use the email address of the intended users (e.g. billbob@yourdomain) and sendmail will relay to Exchange to find them.
Also note you can setup cheap paging from Nagios by sending email to phonenumber@providerdomain (vtext.com for Verizon for example). This sends a text message to the cell phone at the number you used.