I am using this website ---www.xml-sitemaps.com because sitemap.xml that it generates I can deploy it straight away (quick and easy)
The question is wide: there are several different sitemaps that you can create. For search engine optimization, for the most important ones are xml sitemaps. You can create basic xml sitemaps here: http://www.xml-sitemaps.com/ In Wordpress, there are plugins to do it: Google XML Sitemaps or Wordpress SEO. Basically, the reason why you should create xml sitemaps is that they will help the search engines such as Google, Yahoo and Bing to crawl your website and figure out what exactly is in your website. There are also xml sitemaps for images and videos, which is more and more important to have. This site allows you to create HTML Sitemaps (for your visitors use) and ROR Sitemaps. ROR Sitemaps are not very used yet though. XML and HTML sitemaps is what you need to begin with!
We have used gSiteCrawler for all our sitemap.xml needs. It's free, unlimited and handles very large sites.
The best one would be to use google sitemap .... It's made by Google, created for your website, for GOOGLE
Gsite Crawler. If you are using a CMS like WP or Joomla I would recommend you to add their dynamic sitemap plugin. That will create sitemaps dynamically as you add content and just submit that sitemap page rss to google.