Anyone really notice a big traffic difference from search engines in regards to using a sitemap vs not using one?
A sitemap's purpose isn't to get you more traffic, it's to enable pages to be spidered that it might otherwise be difficult to.
sitemap helps spread PR around your site. THe higher PR your internal pages have the better they will rank on searcn engines. so in other words, site maps are a critical part of SEO.
one might think that might be related to traffic Anyways, I've found it works EXTREMELY well for getting all your pages indexed and thus findable by the searchers. If it's easy to get one up, then go for it.
As long as your site is crawable, a sitemap isn't even needed. I certainly wouldn't call it "critical". Sitemaps just give you a way to prioritise crawling of your site and perhaps give SEs a helping hand. The most benefit from the Google sitemaps I get is the handy Webmaster Tools console.