Any good audio editor will do. The problem is when you're working with an existing mp3 of a complete song, you're very limited in what you can do because you cannot remove anything that's already there to replace it with something of your own creation.
Garage Band would be as good as any other; probably better. GB allows for software and real instruments, not to mention the tens of thousands of existing (some free) loops of both real and software instruments which GB supports. Plus Garage Band 2 supposedly supports time stretching and tempo matching with real instrument loops and imported mp3 tracks. I've not tried that myself. If you're a "cut and paste" kind of remixer like I am, GB is good because it does make it very easy to split a song (or loop) at any given point and simply drag and drop chunks into a new order. Add a few loops or tracks of your own to flesh out the whole thing and you're in business.
But true, masterful remixing can only be done when you have access to the individual tracks that make up the song -- take for instance the many, many Garage Band remixes of Nine Inch Nails' recent single which was released as a Garage Band project file. If more bands would do that, I'd be in heaven. I can totally see remixing some of the old classic Depeche Mode, Erasure or Pet Shop Boys songs in Garage Band with each instrument track separated.