I may get chastised for this but I believe the value of sitemaps is over stated.
All things being equal, I feel they are crutches and band-aids for poor webdesign/production.
Your site should:
- be easily indexed by all engines
- expose all pages with in four-five links of the home page(s)
- utilize thoughtful linking to promote important content in an organic manner
- expose new content on a high value, frequently indexed page (ie the home page) long enough to be found
- be consistent enough that the site will seem similar after one or two passes by Googlebot.
I like sitemaps when big structural changes occur as the sites heal faster. They're good when a lots of pages are only exposed via a long pagination scheme. I also use them to break down parts of a site to expose problem areas (IE when a sitemap has 50 links but Google only indexes 25 of them)
But, they can be detrimental if they are not maintained properly. If anything changes in the structure, it should be immediately reflected in the sitemap. Lots of automated ones don't consider the robot.txt file which can cause problems.
For SEOs, adding a sitemap is an easy way to ensure everything is at least looked at without having to touch the actual site.
Advice: yes, use them but only if you can use them properly or can't fix current indexing issues. Over the long haul however, you should force yourself to think of it as not there.