The simplest way to do that is to have the search box code in an include file as part of either the header or footer for each page on your site. It's a good idea to have header and footer includes anyway, as it becomes much easier to change the look and feel of your site, should you ever decide to do that.
If you need a specific example of how to do that, I'd be glad to post some code for you.
