To edit the navigation, along with changing the look of your Nagios interface, all you have to do is open /usr/local/share/nagios/side.html and make your changes. Simply open the file in your HTML editor of choice, or a text editor if you choose.
The HTML below replaced the Nagios logo in this example. After making some changes to the inline CSS, I achieved the look seen above.
<table width="150" border="0"> <tr> <td> <div align="center"><a href="http://www.nagiosbook.org" target="_blank"><img src="images/nagios_book_logo.gif" border="0" alt="NagiosBook.org"></a><br></div> </td> </tr> </table>