You may be better floating the menu left and then surrounding the search box with a div and floating that right, then they should stay on the same line. A float should also have a width (unless it's an image).
ie.
<ul class="menu">
<li class="page_item page_item_1 <?php if ( is_home() ) { ?>current_page_item<?php } ?>"><a href="<?php echo get_settings('home'); ?>/" title="Home">Home</a></li>
<?php wp_list_pages('title_li=&depth=1' ); ?>
</ul>
<div class="search-right">
<form action="http://www.google.com/cse" id="cse-search-box">
<div>
<input type="hidden" name="cx" value="009362889185095370220:iivnc3jfns4" />
<input type="hidden" name="cof" value="FORID:11" />
<input type="text" name="q" size="25" />
<input type="submit" name="sa" value="Search" />
</div>
</form>
<script type="text/javascript" src="http://www.google.com/coop/cse/brand?form=cse-search-box&lang=en"></script>
</div>
then set your CSS as
ul#menu {
width: 60%;
float: left;
}
div.search-right {
width: 35%;
float: right;
}
You may need to play with your widths to get them to fit. Go by the width of the search box as that's the fixed width whereas you may add more pages in the future. Just make sure the two widths add u to either less than 100% or less than the full width of the site if you use pixels (sorry I'm not sure if it's a fixed or flexible width theme).
Because of the floats you may then need to add an additional clearing div below the markup else it could throw other elements out, if you do then insert
<div style="clear:both"></div>
Right after the closing div of the search box.