well.. i guess you want search results and the search box to be on all screens ?
what i'd do is add the div right after the opening body tag and set it's inline style to style="display:none; z-index:10000;" also class="search_results_div" kinda dealio..
so it's hidden all of the time.. (until needed)
your extra css section styles the search_results_div to (when it becomes visible) to appear in the middle and the z-index allows it to overlay anything 'underneath' ...
then your ajax (javascript) crapola would do a .show / .hide (appear/fade if you wanna do scriptaculous stuff).. and then invoke the Google API stuff to fill it up..
... soo since it's right after the opening body tag, the file would be header.tpl

-- forgot to mention it

ps: here is an example of how they did it.. same idea.. just different styles
Linky Poo™Documentation is here