A sitemap is a xml file that is used by (for instance) search engines to get a better overview of your site. It gives details about what pages exists and how ranks the pages towards themselves.
Despite the name the sitemap is not Google specific, it can be used for any search engine, or any other reason that you need a sitemap.
Create a folder for the site map and make it writable
First figure out where to place the sitemap(s) and make that location writable by the webserver.
In a Linux environment this is done from the console this is done like:
mkdir sitemap sudo chown admin:www-data sitemap sudo chmod 775 sitemap touch sitemap/index.php
The touch index.php will create a empty index file (that keeps the folder from being listed.
Define a sitemap
In the admin panel go to “Catalog->Goolge Sitemap->Add sitemap”
Fill out this form with values that makes sense to you.
Note: If you have sveral stores one website, then all product that are visible on that website is added to the sitemap.
Make the site map update automatically
In the admin pangel go to “System->Configuration->Google sitemap”
Another (older) way of doing this is described by the guys at inchoo