To quote the specs:
The nav element represents a section
of a page that links to other pages or
to parts within the page: a section
with navigation links.Not all groups of links on a page need
to be in a nav element — only sections
that consist of major navigation
blocks are appropriate for the nav
element. In particular, it is common
for footers to have a short list of
links to various pages of a site, such
as the terms of service, the home
page, and a copyright page. The footer
element alone is sufficient for such
cases, without a nav element.
So feel free to wrap both in a single nav tag. Don’t wrap the footer but use the footer tag here 🙂
Read the specs here: http://dev.w3.org/html5/spec/Overview.html#the-nav-element