Where do custom menus get constructed?

Try this:

add_filter('wp_nav_menu_items','search_box_function');
function search_box_function {
search box code goes here
}

For reference, check out Bill Erickson’s excellent tutorial on accomplishing this with the Genesis framework.