How is custom menu hierarchy output handled?

• Each nav menu item is stored a post type named nav_menu_item.
• The horizontal position is stored in the column menu_order
• The vertical position (hierarchy) is stored as post meta field named _menu_item_menu_item_parent holding the parent nav_menu_item ID.

To create nested lists WordPress looks for _menu_item_menu_item_parent on each item, and if there is an item with that ID those posts will be grouped in a new sub list. That is basically what the class Walker_Nav_Menu does.

To illustrate that, use a little plugin:

<?php
/**
 * Plugin Name: Inspect Nav Menu Items
 * Plugin URI:  http://wordpress.stackexchange.com/q/70872
 */

add_filter( 'wp_nav_menu_args', 'wpse_70872_inspect_nav_menu_items' );

function wpse_70872_inspect_nav_menu_items( $dummy = 1 )
{
    if ( 'wp_nav_menu_args' === current_filter() )
    {
        add_action( 'shutdown', __FUNCTION__ );
        return $dummy;
    }

    // If we made it so far this function was called on 'shutdown'.
    $nav_items = get_posts(
        array (
            'numberposts' => -1,
            'post_type'   => 'nav_menu_item'
        )
    );

    $out = array ();

    foreach ( $nav_items as $nav_item )
    {
        $out[] = array (
            // general post data
            'post_data' => $nav_item,
            // meta data
            'meta' => get_post_custom( $nav_item->ID ),
            // Name of the menu
            'terms' => wp_get_object_terms( $nav_item->ID, 'nav_menu' ),
        );
    }

    print '<pre>' . esc_html( var_export( $out, TRUE ) ) . '</pre>';
}

The result might look like this:

array (
  0 => 
  array (
    'post_data' => 
    stdClass::__set_state(array(
       'ID' => 695,
       'post_author' => '1',
       'post_date' => '2012-10-29 23:24:13',
       'post_date_gmt' => '2012-10-29 23:24:13',
       'post_content' => ' ',
       'post_title' => '',
       'post_excerpt' => '',
       'post_status' => 'publish',
       'comment_status' => 'open',
       'ping_status' => 'open',
       'post_password' => '',
       'post_name' => '695',
       'to_ping' => '',
       'pinged' => '',
       'post_modified' => '2012-10-29 23:24:13',
       'post_modified_gmt' => '2012-10-29 23:24:13',
       'post_content_filtered' => '',
       'post_parent' => 0,
       'guid' => 'http://wpse.mu.wp/?p=695',
       'menu_order' => 9,
       'post_type' => 'nav_menu_item',
       'post_mime_type' => '',
       'comment_count' => '0',
       'filter' => 'raw',
    )),
    'meta' => 
    array (
      '_menu_item_type' => 
      array (
        0 => 'taxonomy',
      ),
      '_menu_item_menu_item_parent' => 
      array (
        0 => '693',
      ),
      '_menu_item_object_id' => 
      array (
        0 => '12',
      ),
      '_menu_item_object' => 
      array (
        0 => 'category',
      ),
      '_menu_item_target' => 
      array (
        0 => '',
      ),
      '_menu_item_classes' => 
      array (
        0 => 'a:1:{i:0;s:0:"";}',
      ),
      '_menu_item_xfn' => 
      array (
        0 => '',
      ),
      '_menu_item_url' => 
      array (
        0 => '',
      ),
    ),
    'terms' => 
    array (
      0 => 
      stdClass::__set_state(array(
         'term_id' => '105',
         'name' => 'Test 1',
         'slug' => 'test-1',
         'term_group' => '0',
         'term_taxonomy_id' => '106',
         'taxonomy' => 'nav_menu',
         'description' => '',
         'parent' => '0',
         'count' => '9',
      )),
    ),
  ),
  1 => 
  array (
    'post_data' => 
    stdClass::__set_state(array(
       'ID' => 694,
       'post_author' => '1',
       'post_date' => '2012-10-29 23:24:12',
       'post_date_gmt' => '2012-10-29 23:24:12',
       'post_content' => ' ',
       'post_title' => '',
       'post_excerpt' => '',
       'post_status' => 'publish',
       'comment_status' => 'open',
       'ping_status' => 'open',
       'post_password' => '',
       'post_name' => '694',
       'to_ping' => '',
       'pinged' => '',
       'post_modified' => '2012-10-29 23:24:12',
       'post_modified_gmt' => '2012-10-29 23:24:12',
       'post_content_filtered' => '',
       'post_parent' => 0,
       'guid' => 'http://wpse.mu.wp/?p=694',
       'menu_order' => 8,
       'post_type' => 'nav_menu_item',
       'post_mime_type' => '',
       'comment_count' => '0',
       'filter' => 'raw',
    )),
    'meta' => 
    array (
      '_menu_item_type' => 
      array (
        0 => 'taxonomy',
      ),
      '_menu_item_menu_item_parent' => 
      array (
        0 => '693',
      ),
      '_menu_item_object_id' => 
      array (
        0 => '11',
      ),
      '_menu_item_object' => 
      array (
        0 => 'category',
      ),
      '_menu_item_target' => 
      array (
        0 => '',
      ),
      '_menu_item_classes' => 
      array (
        0 => 'a:1:{i:0;s:0:"";}',
      ),
      '_menu_item_xfn' => 
      array (
        0 => '',
      ),
      '_menu_item_url' => 
      array (
        0 => '',
      ),
    ),
    'terms' => 
    array (
      0 => 
      stdClass::__set_state(array(
         'term_id' => '105',
         'name' => 'Test 1',
         'slug' => 'test-1',
         'term_group' => '0',
         'term_taxonomy_id' => '106',
         'taxonomy' => 'nav_menu',
         'description' => '',
         'parent' => '0',
         'count' => '9',
      )),
    ),
  ),
  // … and so on. It is a long list.