Hola a todos, 
 
mi sitemap es este (no todo, es solo un ejemplo)  
Código:
 <?xml version="1.0" encoding="UTF-8"?>
<urlset
      xmlns="http://www.sitemaps.org/schemas/sitemap/0.9"
      xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
      xsi:schemaLocation="http://www.sitemaps.org/schemas/sitemap/0.9
            http://www.sitemaps.org/schemas/sitemap/0.9/sitemap.xsd">
<url>
  <loc>http://www.imperiosweb.com/</loc>
  <priority>1.00</priority>
  <lastmod>2008-10-09T06:06:54+00:00</lastmod>
  <changefreq>daily</changefreq>
</url>
<url>
  <loc>http://www.imperiosweb.com/contacto.html</loc>
  <priority>1.00</priority>
  <lastmod>2008-11-04T06:06:54+00:00</lastmod>
  <changefreq>daily</changefreq>
</url>
</urlset>
  esta ubicado en 
http://www.imperiosweb.com/sitemap.xml 
ahora, yo uso google web masters tools (
https://www.google.com/webmasters/tools/), una vez dentro hay una opcion llamada sitemaps, luego dice 
Add Sitemap, aqui agregas la url de tu sitemap 
Espero haber sido de ayuda,   
santiagoanuncios, dices agregar la url del sitemap al robots.txt... mi robots.txt es este:  
Quedaria asi :   
Código:
 User-Agent: *
Allow: /
http://www.imperiosweb.com/sitemap.xml
  ??? 
Gracias