Recently, I tried to search for a PSP port of the PC game Cave Story using Google, using the search string "cave story psp," and was completely frustrated by the preponderance of articles about the game on sites with PSP sections. A human can quickly see that these articles have nothing to do with the PSP, and that the links are part of the site's chrome. Google and other search engines, however, have no means of discerning this separation. Thus, I propose that in order to give search engines the help they need, site designers should label navigation links as rel="nav".
A more complete, but robust, solution would be to include an attribute for the div element from another XML namespace (say "uri:seo-metadata") that would allow you to specify information like the rel attribute of the a element. For example, a div element could take the following form:
<div seomd:tags="chrome nav"><!-- lots of navigation links --></div>
The contents of the div element would then be marked as being part of the site's chrome and not directly related to the content, and would also be marked as being part of the navigation structure. Such an approach would also be extensible so as to include a mechanism to describe other aspects of a resource for the benefit of search engines. Of course, such metadata would be useful to applications outside of SEO and so it would be more appropriate just to refer to it as a generic metadata stucture that allows you to attach metadata to any arbitrary element. That, however, is a topic for another day.