You can build XML site map using the following free tool www.xml-sitemaps.com/ and HTML site map using www.auditmypc.com/free-sitemap-generator.asp . On my website www.movinguide.com i used GSiteCrawler www.gsitecrawler.com/en/download/ that is also a good tool to generate XML site maps.
How do we specify the priorities. What do they mean ad how do we know which page should be given which priority value
The <priority>N.NN</priority> tags indicate to the spider/crawler the importance of that page to be crawled. So if your site has 10,000 pages, then the spider will crawl those with a <priority> of 1.00, then go to the lower priority ones... The <priority> tag does not have any influence on the ranking of the page... Similarly, the <changefreq> tag tells the spider how often to come back to re-index the page. So both tags help the search engine such as Google, Bing, etc manage their spiders. S
I have used www.xml-sitemaps.com but manually edit the automatically generated XML to change the priority and freq for the pages I think are most important and/or likely be updated. Then I upload it myself to Google Webmaster weekly.