I've been adding Sitemaps for my sites for the past 2 years or so. In all that time I'm at all not certain they have helped in the least. However, the major search engines seem to encourage you to have one, so I'll go along with it. It is so easy to add a XML sitemap for Drupal that there is really no downside.

Download the XML Sitemap module from http://drupal.org/project/xmlsitemap. As usual, I got a big tar.gz file, which for me was xmlsitemap-5.x-1.5.tar.gz. I uncompressed that into a "xmlsitemap" folder on my hard drive with WinZip. I uploaded that whole folder to my Drupal server under the sites/all/modules directory.

Next go into Administer >> Site Building >> Modules and enable the parts of XML Sitemap that you want enabled. You need to at least enable "XML Sitemap". I enabled all 5 options, which are XML Sitemap, XML Sitemap: Engines, XML Sitemap: Node, XML Sitemap: Term, and XML Sitemap: User.

Your sitemap should now be found as sitemap.xml, so the sitemap for this site is www.drupnewb.com/sitemap.xml. You can now submit this sitemap to any search engine that will let you. Each SE has it's own submission process. You can find links to submit your sitemap to Google, Yahoo, and MSN in the README.txt for this module.

So, pretty darn painless.