I have been at this one for awhile now and have been growing increasingly frustrated by the lack of clear and understandable information on it. Figured I would turn to the WP community since you have solved so many other issues through the years.
I have a WP site that uses permalinks. http://www.townsandtrails.com/
One of our popular articles is thus: http://www.townsandtrails.com/salomon-xa-pro-3d-ultra-gtx-trail-runner/
However, Google, in their infinite wisdom, has decided to index this page as: http://www.townsandtrails.com/?p=803
This is just one example of many.
The search engines are using the "ugly" URL, not my "pretty" permalink. WP correctly redirects the "ugly" to the "pretty" when you go to the "ugly"... but it isn't telling google (and others) to update their links.
This is causing us serious problems with SEO.
From what I have read, in order to do this you need to set up 301 redirects. But that is where it gets fuzzy to me. I have found no concise, easy to understand, information about how to do that for a problem like this.
BTW, I did not recently set up these permalinks. They have been in place for over a year, and were in place when this article was written. I do not know why search engines are picking up the 'ugly' links instead.