Google Sitemaps started in June 2005 and although it is in beta from personal experience I can say it works far better then I expected and it would probably work even better if I did regular updates of sitemap.xml. That part should be automated soon so I will gain maximum benefit out of Sitemaps.
How does Sitemaps work?
Simplest description would be as if you submitted all your URL's to Google but instead of doing it manually you submit generated sitemap.xml file to Google which after loading it sends Googlebot to all URL's listed in file. You should be careful with this last part and before submitting sitemap.xml to Google you should to check its content because unless you are using plugin for some CMS there is a big chance that some ancient pages you forgot that they exist and forgot to delete form your server will end up in sitemap.xml since most generators doesn't follow your links but instead generates file based on the content of your directory/folder on server which much faster method and takes lot less resource then following links but it could also pick up zip, gif, jpg files etc. Most generators has options which can be set to avoid such things and prevent unwanted things in sitemap.xml so take your time to set it perfectly.
If you have large number of pages which Google hasn't indexed yet Sitemaps is a must as well as for very large sites which are daily updated over some CMS then Sitemaps is perfect solution if you want your content indexed by Google as fast as possible.
Most common rumor against Sitemaps which keeps repeating itself is that Google punishes pages which submit sitemap although nobody has yet given a proof of that so I would considered such false rumors as spread by competition to prevent others using Sitemaps. Of course if your trying to add spam pages via Sitemaps it shouldn't be a surprise if it doesn't work.
Also one addition, thanks to Sitemaps, Google has indexed this site and World of Photography in matter of days, even more entree page in Croatian has become first for keyword 'web savjeti'.
Sitemaps is constantly improved with additions such as list of keyword most visitors find you (More stats)!