Simply open index.template.php and find the function template_menu(). There you will see all the buttons listed in code bits, just insert the line below inbetween one of those.
The line will have to look like this:
echo '<a href="link"><img name="search" id="search" onmouseover="javascript:document.search.src=\'' . $settings['images_url'] . '/' . $context['user']['language'] . '/search_over.gif\'" onmouseout="javascript:document.search.src=\'' . $settings['images_url'] . '/' . $context['user']['language'] . '/search.gif\'" src="' . $settings['images_url'] . '/' . $context['user']['language'] . '/search.gif" alt="' . $txt[182] . '" style="margin: 0px 0;" border="0" /></a>';
As you can see, all the bold items will need to be changed ..and you also need to make 2 buttons for the rollover to work. Here "search" is used, so just exchange that with yours.