Yo también recomiendo la herramienta
http://www.xml-sitemaps.com/
El te crea el sitemap de una forma rápida, luego conforme voy agregando páginas a mis webs, ya lo voy actualizando a mano.
Además también te crea un sitemap para yahoo.
Y si, los tienes que guardar en la raiz del sitio.