If you have a very large site, it can be an excrutiatingly long wait for the search engines to spider every page. One way to speed up that process is to provide the spiders with a site map. This works especially well if some of your pages are 3 and 4 levels deep in the navigation system. A site map can be only two levels deep, assuming you put a link to the site map on your home page, and all pages are listed on the site map. If Google sees your pages only two levels deep, your PR will be distributed much more efficiently.
Another big advantage of a site map is that you are able to point to your pages using keyword-rich link text, which you may not have been able to do as well in your navigation system. Instant keyword laden backlinks that you control. How sweet is that?
Although Google recommends pages have no more than 100 links, you can safely use more. Keep the file size of the page below 101K, however. If your site is very large, then you probably will have no choice but to make several site maps for different categories.
Another nice little tidbit is that if you have the ability to have custom 404 pages with your hosting company, then take advantage of this by putting your site map on the 404 custom page. This way, if a user gets lost and ends up hitting a non-existant page, he'll land on your site map rather than an error page. Much more user-friendly!
Site maps should be designed to be simple and easy to follow. Do not fill these pages with extraneous code. Instead, give clear, simple, hard-coded links to each page. Feel free, however, to add some descriptive text surrounding the links if you like. This could help theme each link for the search engines.
Finally, if you have a large site, it may be a tedious chore to create a site map. There are not many applications available to automate this process. One that I have found to be useful is SiteXpert. After it generated my site map, I did go back through the code and cleaned it up a little, to make it more efficient, so you might want to consider doing the same. Even with that bit of extra work, however, I still saved loads of time since I didn't have to start from scratch.