Where do custom menus get constructed?

I’ve created a simple menu in wp-admin>appearance>menus called main-nav. Works fine.

However, I’d like to add a custom element to the end of the menu… a search box like the search box in the apple.com menu bar. I can’t work out where the menus get constructed in code. where can I can add this… any ideas?

(I’m using the starkers theme)

EDIT

Thanks to tnorthcutt and hakre for pointing me in the right direction. The solution was to put this code in with the other ‘add_filter’ stuff in my theme’s functions.php

add_filter('wp_nav_menu_items','search_box_function');
function search_box_function ($nav){
return $nav."<li class='menu-header-search'><form action='http://example.com/' id='searchform' method='get'><input type='text' name='s' id='s' placeholder='Search'></form></li>";
}

UPDATE

@tnorthcutt’s solution is great for when you have just one menu on your screen, but if you add second menu it appends the search box to that menu too. How would you target just one menu? i’ve registered my menu’s like so:

register_nav_menus( array(
  'primary' => __( 'Primary Navigation', 'twentyten' ),
  'secondary'=>__('Secondary Menu', 'twentyten' ),

 ) );

..and the secondary one gets shown like this:

wp_nav_menu( array( 'container_class' => 'menu-header', 'theme_location' => 'secondary' ) );