I feel XML sitemaps are very important. They allow Google to know all your pages... dont forget to do an HTML sitemap and add it to your robots.txt
sitemap:
http://www.yourdomain.com/sitemap.html, this last is specially useful for Yahoo and MSN, although Yahoo's siteexployer will allow you to add an XML feed...