Are you asking where the ideas come from or how we go about actually executing them?
Answer to the first question: Ask ten different remixers this, and I bet five will give you completely different answers, and the other five (inlcuding me) will say "I have no idea."
Answer to the second question: there are many ways to do it, and it varies a lot from person to person. How much money are you willing to spend?
If you want to do it for free, there are free programs (modplug, noteworthy composer, synthfont, audacity, and others) and free samples (www.hammersound.net) that will help.
If you want to do it for cheap (relatively speaking), FLStudio seems to be a good place to start. I've never used it, but it's popular and I've heard some top-notch remixes done with it.
In the higher range are programs like Sonar, Cubase, Reason, etc.
As for hardware, it really depends a lot on how you're going to go about remixing, and it varies a ton from person to person. Some (but not all) find it easier to use a midi controller. Some (though not many) use full-blown keyboard workstations. Some do it entirely by mouse.
And then if you want to record live, that adds another set of expenses (mics, mixers, etc).
Whatever your methods, it would probably be a good idea to invest in a decent soundcard. I've used an E-mu 1212M and a Creamware Scope Home card, both of which sound excellent but are a bit complicated and will probably scare the crap out of you if you're just starting. There are probably other people who could do a better job of giving reccomendations here.
It would also be a good idea to get a decent set of headphones. Eventually, if you can afford them, good monitors would also be a worthy investment; however, good monitors are quite expensive, and generally require other gear (mixer and/or poweramp) as well.