Para responder sua pergunta de uma maneira mais assertiva e menos pautada em opiniões, peguei a referência do **W3C** sobre a tag `nav`: [http://w3c.github.io/html/sections.html#the-nav-element][1]

Em tradução livre: 

> O elemento nav representa uma seção de uma página que se vincula a
> outras páginas ou a outras partes da página: uma seção com links de
> navegação.

Ou seja, deve ter a navegação em si, que pode ser no topo, lateral, etc.

E para tirar qualquer dúvida se ainda tiver, veja no mesmo link acima o **Exemplo 10**, copiado aqui a parte relevante:


    <header>
        <h1>Wake up sheeple!</h1>
        <p><a href="news.html">News</a> -
          <a href="blog.html">Blog</a> -
          <a href="forums.html">Forums</a></p>
        <p>Last Modified: <span property="schema:dateModified">2009-04-01</span></p>
        <nav>
          <h2>Navigation</h2>
          <ul>
            <li><a href="articles.html">Index of all articles</a></li>
            <li><a href="today.html">Things sheeple need to wake up for today</a></li>
            <li><a href="successes.html">Sheeple we have managed to wake</a></li>
          </ul>
        </nav>
    </header>

Ou seja, navegação dentro do cabeçalho, nada de ruim aqui, as tags semânticas `header` e `nav` trabalham bem juntas, mostram exatamente o que cada parte do `html` faz.
  



  [1]: http://w3c.github.io/html/sections.html#the-nav-element