Some good piece of advice on why it is important to create a sitemap from Marshall Simmonds, Search / SEO Head at The New York Times / About.com (via PDF).
"Having a Google Sitemap does not guarantee a high listing for your web pages and is intended to benefit site owners, users and the Google search engine. By enabling site owners or web managers to upload and prioritise pages Google can spider pages faster than relying on the Googlebot to locate new or updated pages.
With billions of pages to index it can take time and Google may miss or not index pages in a timely fashion. Using Sitemap technology Google hopes to deliver better searches to its users.
It makes total sense to push new links to users quickly. We don’t want to wait on the engine to deliver results – we want to get content into the engine faster. Whenever it’s possible, we opt to push content rather than have it pulled. That gives us a more interactive experience with Google."