Is the search box part of your HTML markup, or is it generated by your script (as linked to above)? Or is it hosted on another domain entirely and displayed with an IFRAME?
Where is your script element? IF your search box is generated by script and you are linking to the script in the HEAD section then try moving the script element to before the closing </body> tag. Although, depending how the script is written, this might not make any difference. Bascially, if the search box is created by script and the script is waiting for your entire page to load before generating it then you are going to see a delay. ...but it could depend on other factors regarding your page structure.
I have added the script within my html and it is a .php script which runs from another domain.... the search box displays on my website but with a 'split-second' delay in loading from the rest of my web pages.
Without too much of a code rewrite I would have thought that the best/easiest solution would be to not concentrate too much on actually speeding it up, but just make it look quicker by including some kind of placeholder where the search box should go and switching this with the real search box once it has loaded - minimising the 'page flicker'. The placeholder could even be a static image of the real search box? Or simply a "Loading..." message?