wow, some interesting responses. I have been painstakingly trying to get my sitemap to function and debating over the priority to give sections and subsections. I need to read the SEO forums more often
Are you talking about the xml sitemap or the html one now? The html sitemap should look like the rest of your site and be linked from every page, preferably at the bottom. All search engines will find this sitemap if it's linked properly. If you're using it, the xml sitemap should be submitted directly to the search engines, but not link from your site. (That would be bad for users.)
i think sitemap should be a good thing to have.. especially that if your site is not a very small site, Google wouldn't know or wouldn't go far by crawling every page, but with sitemap it can and it will (most likely) or at least it would know where to go, rather then just crawling first few pages and giving up on rest...
I'll leave mine there since the xml file is in yahoo and msn' index. It can't hurt. Although I do believe the indexing and PR come from the backlinks, not from the sitemap.