There are different types of sitemaps, with two main users of them, search engines and site visitors.
Site maps designed for visitors are usually not as comprehensive as those designed for search engines and are easier to navigate. They rarely link to every page on a site, as that can easily require hundreds, thousands, tens of thousands or even more in the case of really big sites of links, the links are clickable, and their function is to help a visitor find a section of the site they are looking for.
The text for the links will describe what the linked to page contains in a manner that is useful for a site visitor, so, for example, the link to the sites' forum would be called Forum.
Although this type of site map can be used by search engines, their primary users are visitors to the site, and they are designed in such a way.
Site maps designed for use by search engines will attempt to list as many pages of the site as possible, preferably every page, helping the search engines spider as much of the site as possible.
There are a number of different ways of doing this.
You could manually create site maps, and probably will for those designed for visitors, but ones created for search engines should be created automatically or dynamically, as these will alter as new content is created, although a site with static content will not require updating. Sites that have new content added frequently, whether weekly, daily or even more often, especially on sites with user-submitted content and a large user base, require an automatically updating or dynamically generated sitemap.
RSS Feeds. As mentioned earlier, these will automatically update if designed properly, although these should not be used to index an entire site, but rather new content, so it gets indexed faster.
PHP. It's possible to create a PHP page that will create a clickable list of links of all the pages on your site that you want indexing, although on big sites this will probably increase the server load more than is desired.
WordPress. There are plugins (such as Google XML Sitemaps) that allow WordPress to automatically create a new XML site map on a regular basis, with many customisation options, and also to submit the sitemap to Bing, Google and Ask when it is updated.
There are some web services that will create a site map for your site for free, if you submit the domain, although these do have limits to the number of pages you can index, and should only really be used for static sites, as a new site map would need to be created and uploaded to your server every time new content was added.
A Word of Warning
Some scripts that automatically create and update your sitemaps require altering the Linux permissions (based on the similar Unix notation) of the files that will be created or rewritten to 666, as opposed to the normal 644. This is a security risk, and should not be done. By altering a file's permissions to 666, you are allowing anyone who knows what they are doing to alter that file, creating a vulnerability to crackers.
Submitting Site Maps
Registering a site with Google, Bing, Yahoo or Ask Webmaster Tools will allow you to submit sitemaps to those search engines to help them crawl your site. There is no limit to the sitemaps you can add, and multiple formats are supported.