How do I add support to my theme for custom menus?

The easiest way is to use the register_nav_menus function.This should be hooked into 'after_setup_theme':

function my_cool_menu_function(){
  register_nav_menus( array(
    'primary' => 'Primary Navigation'
  ));
}

add_action( 'after_setup_theme', 'my_cool_menu_function' );

Then, in your theme, simply call that menu’s position:

wp_nav_menu( array( 'theme_location' => 'primary' ) );