Interspire Product Knowledge Base

First, you'll need to setup a Google Webmasters Account  at:
www.google.com/webmasters

Once you've set that up and proven to Google that you exist using one of their two methods, then it's time to create your sitemap.

Browse to your store and add a "/sitemap.php" at the end of the URL. In other words, if your store is located at:
www.mystore.com, then you'd be pointing your browser to www.mystore.com/sitemap.php

The resulting page is an XML file and you'll need to click "File" and then "Save As" from the browser menu. Save it somewhere where you can find it again (I usually drop it on my desktop). Now upload that file via FTP to your website...again somewhere easy to type so that you can tell Google where it is in a minute.

Now point your browser to:
https://www.google.com/webmasters/tools/dashboard
and click the "Add" link in the Sitemap column.

Now choose the "Add General Web Sitemap" option and enter the URL of your sitemap.