There is an updated version of this article for WordPress 3, see Move the search box to the header – WordPress 3 revision
The default theme in WordPress places the search box in the sidebar. Moving it to the header is relatively easy to do if you’re comfortable making minor changes to the code. The first thing is to find the path to the theme that you are using, for the default theme the path is:
Then using your favourite text editor open up the following files:
Note: Before you make any changes to these files make sure you have a backup
Next look for the following code fragment in sidebar.php which is used by WordPress to generate the search box (What this code does is to insert the contents of the searchform.php file at this point in the page. The searchform.php file contains the code to produce the search box and the search button).
<?php include (TEMPLATEPATH . '/searchform.php'); ?>
Cut the line of code above from the sidebar.php file and paste it in an appropriate location in the header.php file.
This will move the search form from the sidebar to the header. The end result may look strange because of the CSS styles in use. To get the result seen above in the header of this blog I changed the stylesheet to make the title float left and the search form float right, where you place the search form is down to personal preferences.