I would avoid using headings for navigation on the whole. The headings should be about the specific content of the page, not the architecture of the site overall. Keep the navigation in an unordered list.
Ouch! That one is going to cause some stir. I do believe many of us have followed the long standing suggestions of placing menu items in lists and preceding them with headings if they are within a left/right navigation menu. Interesting that you would avoid headings in this instance as I see the assistive technologies rely on these to help define structure for the user. We'll definitely need to expand on this one. How would you precede a list of links that define a section? For example, you have 5 links in one section, 5 in another and 5 in another. They are three distinct sections that all have a root level Table of Contents and fall under a specific category. How would you label those lists?
Hi POR - to clarify, I would not use headings to denote individual nav elements - no problem with putting a heading referring to the nav as a whole.