Override Menu markup

Drupal core outputs menus like this:

<div id="main-menu" class="navigation">
  <h2>Main Menu Title</h2>
  <ul id="main-menu-links" class="links clearfix">
    <li>Link 1</li>
    <li>Link 2</li>
  </ul>
</div>

We want instead to be:

<nav id="main-menu">
  <h2>Main Menu Title</h2>
  <ul id="main-menu-links" class="links clearfix">
    <li>Link 1</li>
    <li>Link 2</li>
  </ul>
</div>

Only we should talk about the id and classes on <ul>. And about whether the title should be <h1> or <h2>.