nav is used for groups of internal links (a elements). Generally this means the links should travel to separate pages, or change content in the case of an AJAX page. Expect some sort of content change when clicking on a nav item.
menu is used for groups of controls (a, input, button). Generally this means the inputs should perform a function within the page. Expect some sort of javascript interaction when clicking on a menu item.
<nav> is a section (like <section> or <article>) so it will appear in your HTML document outline. Due to this, I would use <menu> 99% of the time. To me, <nav> is a mix between <section> and <menu>, with the added constriction that <nav> should be used specifically for navigation, whereas <menu> can be for anything that might be called a menu (including a navigation bar). So most navigation bars, despite the fact that they are navigation bars, do not fit the strict requirements of <nav>, and <menu> is more appropriate.
I have never in my web development career found a situation where I wanted my navigation bar to be part of the document outline.