I just enabled WordPress Permalinks in my blog. The links look much better than the ugly querystring URLs before.
It might take a while for the redirection to kick in so wait for 5-10 minutes. In my case it was instant though. And in case you were wondering what happens to the URLs already indexed by the search engines, they work as well!!!