In your template/sideboxes/tpl_search.php

around line 22 put this code in starting with <input type

<input type="image" name="search" src="includes/templates/your-template/buttons/english/button_search.gif"/>

Believe me when I say it took me hours to figure this one out for myself.