The difference between the two in my eyes is that one of the plugin sends link to the sitemap and the other just notifies the service that a new post has been made. I will also explain a little further upon the two, if I am wrong someone please correct me.
The sitemap plugin generates a sitemap in which a web spider can crawl and see all of your pages. It is just an XML file listing all of your pages and a bit of other information that is useful to spiders. The file is gzipped (.gz) so that it can save bandwidth. Pure .gz files are uncompressed on the fly in your browser, so if you would like to see the XML file you can just open it up in your browser. You should not notice a difference between this file and if it were named filename.xml.
To go a little further, in PHP it allows for gzipping the content to save bandwidth. It is possible to enable this by default, but most servers do not have this enabled. That is why there is the option to turn it on in most web based applications, serendipity has this.
The other plugin is for pinging web based services to tell them that you have a new post. In a way it sends them a link to new posts so that they can link to it. These services do not want to list the same thing multiple times and therefore the plugin only sends out the pings when you have sent a new post.
There are quite a few services out there to send these pings out for you. I use
feedburner which allows me to do this. If you have not heard of feedburner I suggest taking a look at it as it does a bunch of neat things with your RSS/ATOM/whatever feeds.
In all these services are there to help people find your blog, especially when you have added something new. One is a directory of sorts (pinging services) and the other is search engines. It is a good idea to use both to bring in the most people, as isn't that the point of a blog?