OOPS: The below is for moving search to the right sidebar. I just realised that wasn’t what you asked for!
I have done this for one of my templates. I am doing this from the top of my head as it’s not in front of me, but the GIST is below. You WILL have to complete other steps to get it working.
1. Make a copy of magento\app\design\frontend\default\avocado\template\reports\product_viewed.phtml and save it as magento\app\design\frontend\default\avocado\template\catalogsearch\search.phtml.
product_viewed.phtml acts as the basic skeleton of a sidebar box. We now paste the search form code into it.
2. Open search.phtml and remove clutter to give you the basic skeleton:
<div class="box base-mini mini-search">
<h4><span><?php echo $this->__('Search') ?></span></h4>
<!-- PASTE SEARCH CODE HERE -->
NOTE: I have removed the PHP if statement from around this code. The search box will not show otherwise. I have also changed the class name of the box to mini-search.
2. Open magento\app\design\frontend\default\avocado\template\catalogsearch\form.mini.phtml. Copy the code and paste it into the content div in search.phtml (marked above).
3. Open magento\app\design\frontend\default\avocado\layout\catalogsearch.xml. Add the following under the <default> attribute:
<block type="catalogsearch/search" name="right.catalogsearch.search" template="catalogsearch/search.phtml" />
4. Open boxes.css and edit the .mini-search attributes. You will need to get rid of the position: absolute line plus some others.
Like I say I am doing this from memory so there may well be errrors. But at least you get the idea.