A sitemap is used to inform search engines about pages availabe for crawling. Magento provides a built-in function to generate a standards compliant sitemap in XML format containing the URLs for Category pages, Product pages and CMS pages.
While Magento refers to these sitemaps as "Google Sitemaps", they are actually supported by Yahoo! and Microsoft bing as well.
To add a new sitemap, you will first need to create a /sitemap directory in your web root directory with writable permissions so that you can generate and save to that location (http://www.example.co.nz/sitemap/sitemap.xml or similar). Then go to Catalog > Google Sitemap and add a new sitemap.
To "refresh" your sitemap at regular intervals, go to System > Configuration > Catalog > Google Sitemap > Generation Settings. Set to yes and create in the early hours of the morning.
To provide your sitemap to the search engines, you can link to it from your robots.txt file, which you should find in your web root directory (e.g. http://www.example.co.nz/robots.txt). Use the following sitemap directive, substituting example.co.nz for your own domain of course:
You should also register your sitemap manually with the Google and Microsoft:
Google Webmaster Tools: https://www.google.com/webmasters/tools/
Bing Webmaster Tools: http://www.bing.com/webmaster/