How to customize navigation menu?

Using wp_nav_menu() and a Walker is a great thing and I really appreciate the other answers with this solution, but I think it’s a really hard way to go for a simple menu. So I found myself quite often doing it via wp_get_nav_menu_items()

So let’s focus on the idea: I just get all the menu items from one of the WordPress navigation menus to completely re-build the menu myself.

What I get is a strip naked menu as we’ve once seen it as we learned HTML. The output will look like this:

<ul>
    <li></li>
    <li></li>
    <li></li>
    (...)
</ul>

First and last of all we need the name of the menu registered in the menu manager. You’ll probably find this in your functions.php. This is for example what it looks like in the Twenty Thirteen-Theme:

register_nav_menu( 'primary', __( 'Navigation Menu', 'twentythirteen' ) );

Besides this we’ll not need to insert any more information manually because we’ll be able to get the details (e.g. location, id,…) of the registered menu:

<?php
    $menu_name="primary"; // this is the registered menu name

    if ( ( $locations = get_nav_menu_locations() ) && isset( $locations[ $menu_name ] ) ) :
        $menu = wp_get_nav_menu_object( $locations[ $menu_name ] );
        $menu_items = wp_get_nav_menu_items($menu->term_id);
        echo '<ul>';
            foreach ( (array) $menu_items as $key => $menu_item ) :
                $title = $menu_item->title;
                    echo '<li>' . $title . '</li>';
            endforeach;
        echo '</ul>';
    else :  
        echo '<p>Menu "' . $menu_name . '" not defined.</p>';
    endif;
?>

So this will echo a simple menu structure completely without classes and with the menu items form your navigations menus manager; or it will fail smoothly if the menu name or the location is not (yet) defined.

With all this in mind you should have no trouble to add your own sorting or whatever… just take a look at the wp_get_nav_menu_items() default parameters (as provided in the Codex):

<?php 
    $args = array(
        'order'                  => 'ASC',
        'orderby'                => 'menu_order',
        'post_type'              => 'nav_menu_item',
        'post_status'            => 'publish',
        'output'                 => ARRAY_A,
        'output_key'             => 'menu_order',
        'nopaging'               => true,
        'update_post_term_cache' => false 
    ); 
?>

UPDATE: To summarize my answer and to focus on the last part of your question: this will not harm you (it’s only about the styling), but it will also not provide any kind of extra functionality (like extra classes for current pages or things like that). You’ll have to build all extra functions by yourself.

So you’ll have a good go to use wp_nav_menu(); simply ignore all these id and class names within the source code of your page if you do not need them, but they will be there if you’ll need them in the future 🙂