How to change theme header to support multiple nav menus?

First off, some things you should know about nav menus:

1. Menus are simply terms in a taxonomy called nav_menu.
2. Menu items are a special post type

In short: menus are just like nearly every other piece of content in WordPress, they just have a custom UI.

With that out of the way, the task is fairly simple: put a custom meta box on your edit screen that shows options to choose nav menus. On the front end, switch the nav menu out to whatever you set in the admin area. The only thing to worry about is what the theme_location value is for your theme’s call to wp_nav_menu. Where do you want to switch the menu out?

This is example will use Twenty Twelve, which uses the theme location primary.

A call to wrap everything up in:

<?php
class PerPostNavMenu
{
    const NONCE = 'wpse85243_nav_nonce';
    const FIELD = '_wpse85243_per_post_menu';
    const LOC   = 'primary'; // the location for twenty twelve

    private static $ins = null;

    public static function instance()
    {
        if (is_null(self::$ins)) {
            self::$ins = new self;
        }

        return self::$ins;
    }

    public static function init()
    {
        add_action('plugins_loaded', array(self::instance(), '_setup'));
    }

    public function _setup()
    {
        // we'll add actions/filters here later
    }
}

Now let’s add our meta box. Since this is covered in detail a great many places, I’ll give the cliff notes explanation: hook into add_meta_boxes, call add_meta_box. In the meta box callback function, output a nonce and your field(s).

To save the values, hook into save_post, check to make sure we are where we want to be (no autosave, nonce validates) and that the current user can edit the post, save (or delete) the value with (update|delete)_post_meta.

<?php
class PerPostNavMenu
{
    const NONCE = 'wpse85243_nav_nonce';
    const FIELD = '_wpse85243_per_post_menu';
    const LOC   = 'primary'; // the location for twenty twelve

    // snip snip

    public function _setup()
    {
        add_action('add_meta_boxes', array($this, 'addBox'));
        add_action('save_post', array($this, 'save'), 10, 2);
    }

    public function addBox($post_type)
    {
        if (!post_type_exists($post_type)) {
            return;
        }

        add_meta_box(
            'wpse85243_nav_menu',
            __('Nav Menu', 'wpse'),
            array($this, 'boxCallback'),
            $post_type,
            'side',
            'low'
        );
    }

    public function boxCallback($post)
    {
        $menu = get_post_meta($post->ID, static::FIELD, true);

        wp_nonce_field(static::NONCE . $post->ID, static::NONCE, false);

        printf(
            '<label for="%s">%s</label>',
            esc_attr(static::FIELD),
            esc_html__('Nav Menu', 'wpse')
        );

        echo '<br />';

        printf('<select name="%1$s" id="%1$s">', esc_attr(static::FIELD));

        foreach ($this->getNavMenus() as $id => $name) {
            printf(
                '<option value="%s" %s>%s</option>',
                esc_attr($id),
                selected($menu, $id, false),
                esc_html($name)
            );
        }

        echo '</select>';
    }

    public function save($post_id, $post)
    {
        if (defined('DOING_AUTOSAVE') && DOING_AUTOSAVE) {
            return;
        }

        if (
            !isset($_POST[static::NONCE]) ||
            !wp_verify_nonce($_POST[static::NONCE], static::NONCE . $post_id)
        ) {
            return;
        }

        $type = get_post_type_object($post->post_type);
        if (!current_user_can($type->cap->edit_post, $post_id)) {
            return;
        }

        $menu = isset($_POST[static::FIELD]) ? $_POST[static::FIELD] : false;

        if ($menu && '-' !== $menu) {
            update_post_meta($post_id, static::FIELD, absint($menu));
        } else {
            delete_post_meta($post_id, static::FIELD);
        }
    }

    private function getNavMenus()
    {
        $terms = get_terms('nav_menu');

        $menus = array('-' => __('Default', 'wpse'));
        if ($terms && !is_wp_error($terms)) {
            foreach($terms as $t) {
                $menus[$t->term_id] = $t->name;
            }
        }

        return apply_filters('per_post_nav_menus_list', $menus);
    }
}

Notice the helper method to retrieve the nav menus. Not much, just a convenient helper that runs the result through a filter.

Finally, we just need to switch out the menu. To do that, hook into wp_nav_menu_args and, if we’re on a singular page and have the correct theme location, switch out the menu as appropriate. Some extra filters are included to make this a bit more extensible.

<?php
class PerPostNavMenu
{
    const NONCE = 'wpse85243_nav_nonce';
    const FIELD = '_wpse85243_per_post_menu';
    const LOC   = 'primary'; // the location for twenty twelve

    // snip snip

    public function _setup()
    {
        add_action('add_meta_boxes', array($this, 'addBox'));
        add_action('save_post', array($this, 'save'), 10, 2);
        add_filter('wp_nav_menu_args', array($this, 'switchMenu'));
    }

    // snip snip

    public function switchMenu($args)
    {
        // we can only deal with singular pages
        if (!is_singular()) {
            return;
        }

        $switch = apply_filters(
            'per_post_nav_menus_switch',
            isset($args['theme_location']) && static::LOC === $args['theme_location'],
            $args
        );

        // if we're allowed to switch, the the `menu` argument to
        // the correct menu ID.
        if ($switch) {
            $menu = get_post_meta(get_queried_object_id(), static::FIELD, true);

            if ('-' !== $menu) {
                $args['menu'] = absint($menu);
            }
        }

        return $args;
    }

    // snip snip
}

All of the above as a plugin.