General information
While Magento is a powerful e-commerce platform there are some drawbacks which you should do manually on every new site. For example, we cannot configure one sitemap.xml for one store with different store views, these should be three different files. It brings some misunderstanding how all should work together.
System configuration
- Go to
System>Configuration>Catalog>Google Sitemap>Generation Settingsand enable Sitemap generation:

- Go to
System>Configuration>Catalog>Catalog>Sitemapand configure options: Use Tree Like Category Sitemap, Minimum Lines per Page - Switch to the
Search Engine OptimizationTab and Enable the option Autogenerated Site Map

Sitemaps directory
Connect to your site with your favourite client (FTP/SSH) and create sitemaps/ in the project root directory.
Sitemap configuration
- Navigate to
Catalog>Google Sitemap>Add Sitemap - Add a sitemap.xml file to the configuration:

- Configure others sitemaps. It can be like as on the screenshot

Sitemap generation
Now you can generate sitemaps manually by clicking Generate button in Action column or setup crontab and your sitemaps will be generated automatically.
Register sitemaps in robots.txt
You can just generate the sitemap.xml per store.
In your robots.txt add the path to the sitemaps, for example:
# Sitemap
Sitemap: http://www.yourdomain.com/sitemaps/sitemap_en.xml
Sitemap: http://www.yourdomain.com/sitemaps/sitemap_ua.xml
Sitemap: http://www.yourdomain.com/sitemaps/sitemap_ru.xml