Depending on the Site size, a sitemap is a good recommendation.

Personally I would include an XHTML sitemap for good measure for sites over 20 pages and a Google Sitemap for sites with about 50 pages or more.

IMO - I haven't seen any real value for webmasters to worry themselves too much with Google XML Sitemaps until they reach a minimum of 50-100 pages.

But that's just my opinion.

Qualifier:
Those Sites should have clear cut textural paths laid out as "flat" as possible. If you are in the javascript camp for Nav with gnarly garbage like "swap images", I'd have a sitemap starting at 2 pages!

Ken