When building an html sitemap your main focus should probably be on usability. I like to use it to help my site users navigate the site better (especially since the XML sitemap will take care of feeding the search engine bots). Some webmasters have moved away from HTML sitemaps and instead have added search boxes to their sites. You may want to search for other websites HTML sitemaps to see the different layouts.
When building the XML sitemap you should consult each search engine's guidelines to make sure it is formatted how they like it. If you site has good internal navigation, a nice amount of inbound links and the pages are properly interlinked you will probably not gain much with an xml sitemap. Hope that helps.