role="navigation"はどの要素に書くのが良いのだろうか
基本
HTML5に関して言えば基本的にはどの要素にも書かない、と考えています。
もともと、role="navigation"はその要素がナビゲーションランドマークであることを示します。そしてHTML5では、主要なナビゲーションを表すnav要素が新設されました。このnav要素は暗黙的にナビゲーションランドマークとなることが仕様に書かれていますので、nav要素を使えばrole="navigation"を書く必要は基本的にありません。
もう少し明確に書くと、「暗黙的にナビゲーションランドマークとなる」は「nav要素のStrong native semantics（とdefault implicit ARIA semantics)はnavigation roleである」を指し、「仕様」も以下のものを指してます。
蛇足を続けると、Strong native semanticsは要素が本質的にもっていてrole属性で上書きできないセマンティクスのことです。つまりnav要素は暗黙のうちにrole="navigation"であり、それを変更することはできないということになります（role="presentation"という指定はできますが…）。なので、nav要素を使うかぎりrole="navigation"は基本的に不要です。
例外
基本があれば例外もあります。
nav要素は暗黙的にナビゲーションランドマークとなる、と書きましたが、この暗黙的な対応付けはブラウザーなり支援技術なりが行います。ブラウザーや支援技術が対応付けを広くサポートしていれば、nav要素にrole属性を書く必要性はありません。
しかしながら、Using ARIA in HTMLのEditor's Draft（2013年9月2日閲覧）を見ても、「nav要素の対応付けは、ブラウザーで広くサポートされているわけではないので、デフォルトのARIAセマンティクスは明示的に書く（nav要素にrole="navigation"を指定する）べき」とされています。具体的にどの実装がどう、あの実装がどうという話はしませんが、私個人としても現時点では書いた方が良いと思います。
ただ、これは現在が過渡期という例外的な時代のためであって、必ずや過渡期は終わりnav要素にrole属性を書かない時代が来るものと信じています。
その他の要素
HTML5にnav要素がある以上はnav要素を使うのが自然だと私は思います。
HTML5 スタンダード・デザインガイドで紹介されているAppleのWebサイトにはul要素にrole="navigation"が指定されていました（と、思うのですが今手元に本がないため、記憶に頼ってこの文を書きました）。しかし、ナビゲーションリストを表現するにはnav要素の子供にul要素を記述するのが自然だと私は思います。これはリンク画像を表現するには、a要素の中にimg要素を記述するのと同じことだと思っています。
…そもそもHTML5の要素に設定できるrole属性値は、デフォルトのセマンティクスと乖離しないように制限されており、ul要素にはrole="navigation"は指定できません。詳細は「仕様」を参照ください。
