Вот несколько ссылок по данной теме:
Википедия
Официальный сайт
Файл sitemap.xml действительно помогает индексации сайта поисковыми системами и ускоряет этот процесс. Для WordPress есть неплохой plugin — Google XML Sitemaps, который позволяет строить файл sitemap.xml автоматически. Plugin можно скачать вот с этой страницы. Этот plugin хорош еще тем, что он сжимает файл в формат GZIP, что ускоряет скачивание файла поисковыми ботами.
Кодировка файла должна быть UTF-8, располагаться он должен в корневой директории Вашего сайта. Подробно назначение тагов файла описано на втором ресурсе. Вот пример блока xml для этого сайта:
<urlset 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" xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
<url>
<loc>http://soft.consulting–plus.com/</loc>
<lastmod>2011–02–22T10:20:31+00:00</lastmod>
<changefreq>daily</changefreq>
<priority>1.0</priority>
</url>
<url>
<loc>http://soft.consulting–plus.com/?p=418</loc>
<lastmod>2011–03–22T10:21:02+00:00</lastmod>
<changefreq>monthly</changefreq>
<priority>0.6</priority>
</url>
<url>
<loc>http://soft.consulting–plus.com/?p=414</loc>
<lastmod>2011–03–07T13:57:54+00:00</lastmod>
<changefreq>monthly</changefreq>
<priority>0.6</priority>
</url>
<url>
<loc>http://soft.consulting–plus.com/?p=406</loc>
<lastmod>2011–03–06T17:12:54+00:00</lastmod>
<changefreq>monthly</changefreq>
<priority>0.6</priority>
</url>
</urlset>
Если Вы не используете WordPress, то Вам придется создавать файл вручную. В статье на Википедии описано, как проинформировать некоторые поисковые системы о том, где находится Ваш sitemap.xml, но я обычно регистрирую файл напрямую в поисковой системе, и делаю это только для Google и для Yandex. Как это сделать, смотрите в соответствующих разделах для поисковиков.