I always put a Links module/skinobject into the site Skin somewhere.  This can be down the bottom, but will be more search engine friendly if you put it somewhere near the top.   This way everyone, whether java enabled or not (not just search engine spiders) can use the site.

I'm 99% certain Google reads the standard DNN menu OK but you might want to think about other bots, as mentioned already.  Most visitors to sites I control don't use the menu anyway - they like to use links in the page text as these are more contextual and more likely to get clicked on.

Inventua have a side-menu which is pretty simply hrefs rather than too much javascript. 

Every site you build you should check out in the lynx text browser.  Not only because this is how a search engine bot will see your site, but plenty of people use non-standard browsers, particularly those with impaired vision who may use a text-reader.  It's free to download and install and will give you great insight into building sites that are well structured and navigable by hrefs only.  It will also give you an insight into how to properly tag your image/flash content so that it makes sense to bots and text readers.