Edit header.php and paste between
<div id="header">
<h1><a href="<?php bloginfo('url'); ?>/"><?php bloginfo('name'); ?></a></h1>
<small><a href="<?php bloginfo('url'); ?>/"><?php bloginfo('description'); ?></a></small>
<div style="clear: right;"></div>
</div>
and
<ul id="navigation">
<li class="<?php if (!is_page()) echo "current_page_item" ?>"><a href="<?php bloginfo('url'); ?>">Blog</a></li>
<?php wp_list_pages('title_li='); ?>
</ul>
this:
<?php if (get_search_query()) { $search = get_search_query(); } else { $search = __("Search"); } ?>
<form method="get" action="<?php bloginfo('home');?>">
<input style="position:absolute;margin-left:636px;top:0px;width:150px;border:5px solid #0F0E0E;padding:2px;" type="text" name="s" id="s" onclick="if(this.value == '<?=$search;?>'){this.value=''}" value="<?=$search;?>" />
</form>
If your are too lazy, you can use this modificated version:
http://up.newroots.de/dev/themes/sidebarssuck/sidebarssuck-1.1.8-wp-searchmod.zip
(Don’t worry, 1.1.7 and 1.1.8 are completely equal)
In v1.2 add “Widgets -> Search”