What you are asking is not an easy change, but this should get you started.
In skin1/head.tpl find
Code:
{if $main ne "fast_lane_checkout"}
<tr>
<td class="HeadLine" height="22">
{if $usertype eq "C"}
{ include file="customer/search.tpl" }
{/if}
</td>
<td class="HeadLine" align="right">
{if ($usertype eq "C" || $usertype eq "B") && $all_languages_cnt gt 1}
Move {include file="customer/top_menu.tpl"} from higher in head.tpl so it is like this
Code:
{if $usertype eq "C"}
{ include file="customer/search.tpl" }
{ include file="customer/top_menu.tpl" }
{/if}
You will find that you will need to edit skin1/customer/top_menu.tpl because it includes a routine to display company phone numbers, but it should get you started.
What I did was included search.tpl in top_menu.tpl like this (My top_menu.tpl)
Code:
{* Modified to include customer/search.tpl in title bar *}
{if $printable ne ''}
{include file="customer/top_menu_printable.tpl"}
{else}
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr><td>
{if $speed_bar}
<table border="0" cellpadding="0" cellspacing="0">
<tr>
{section name=sb loop=$speed_bar}
{if $speed_bar[sb].active eq "Y"}
<td>{include file="customer/tab.tpl" tab_title="<a href=\"`$speed_bar[sb].link`\">`$speed_bar[sb].title`</a>"}</td>
<td width="10"><img src="{$ImagesDir}/spacer.gif" width="1" height="1" border="0" alt="/" /></td>
{/if}
{/section}
</tr>
</table>
{/if}
</td>
<td align="right">
{if $usertype eq "C"}
{include file="customer/search.tpl"}
{/if}
</td></tr>
</table>
{/if}
Search is after the "tabs", and I modified tab.tpl also to eliminate the borders around them. It produces a "bar" that has the speedbar links on the left and the search box on the right. I don't use the alternate languages, so it didn't concern me.
Good luck!