There are two types of sitemaps, HTML and XML. HTML sitemaps are typically for users, while XML are for the benefit of search engines.
Both should list all the pages in your site, HTML in a logical site structure and XML in any order. The search engines use XML sitemaps to get an indication of the number of pages in a site. As well as the URL, XML sitemaps can list a priority, change frequency and last modified date for each page.
XML sitemaps can also be split up according to sections in the site e.g. products, categories, news. They should be referenced in the site’s robots.txt and submitted to webmaster tools, while HTML sitemaps can be linked to in the footer.
Neither of these are essential however they can help the indexing of larger sites.