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”

As always, change to values that makes sense to you

Another (older) way of doing this is described by the guys at inchoo