Moron Proof Way to change URL

Guys, I have a problem. I just did a back link check on my blog and found out that the domain name used to belong to someone else. The previous owner was using it for, shall we say, nefarious purposes and there’s a bunch of spammy incoming links from all sorts of icky places which is going to negatively affect the way the site ranks in search results. I am most distressed. I figure it will be easier to change to name of the blog than trying to track down webmasters and hope they will remove their links.

I need easy, moron proof instructions on how to do change my blog url or would it be easier to take down the blog, set up a new one and transfer all my old posts?