I guess you would have to adjust the height of the logo area in common.css called header-box (or use an image that fits the area)
Then you would need to replace the searchbox to a new location in overall_header.html (removing it from the page_header div block)
That would be this piece of code:
<!-- IF S_DISPLAY_SEARCH and not S_IN_SEARCH -->
<div id="search-box">
<form action="{U_SEARCH}" method="get" id="search">
<fieldset>
<input name="keywords" id="keywords" type="text" maxlength="128" title="{L_SEARCH_KEYWORDS}" class="inputbox search" value="<!-- IF SEARCH_WORDS-->{SEARCH_WORDS}<!-- ELSE -->{L_SEARCH_MINI}<!-- ENDIF -->" onclick="if(this.value=='{LA_SEARCH_MINI}')this.value='';" onblur="if(this.value=='')this.value='{LA_SEARCH_MINI}';" />
<input class="button2" value="{L_SEARCH}" type="submit" /><br />
<a href="{U_SEARCH}" class="" title="{L_SEARCH_ADV_EXPLAIN}">{L_SEARCH_ADV}</a> {S_SEARCH_HIDDEN_FIELDS}
</fieldset>
</form>
</div>
<!-- ENDIF -->
Possibly put it below <!-- INCLUDE menu_block.html --> or <!-- INCLUDE breadcrumbs_main.html --> (but it's a matter of taste
)
and then you'ld need to check how it starts looking because I wrote this without trying
