You might be better off asking this question in the sound department. There is nothing about video in there yet, just about the karaoke soundtrack...
Doing this manually and have it sound good I would call "pretty hard" to do. If you want to spare yourself lots of work and frustration, I would go ahead and search for "Call me maybe karaoke" and buy whatever you find. It will cost you a few bucks at most, and save you lots of pain.
If you still want to do it and you are just starting out and are not sure you want to do this kind of thing very regularly, you should be fine with GarageBand and/or the free
Audacity for the sound part.
The basic idea is that on most professional recordings, the instruments are distributed in the stereo room (e.g. the guitar is a little to the left, the drumset is to the far right, ...), but the lead singer is exactly in the center of the mix. You can now "get rid" of that lead singer if you "phase invert" one of the channels and add them to each other. Then everything that had an exactly equal signal on both sides will be cancelled out (the voice), but the rest will still roughly sound the same. Since the bass is often mixed in the center, too, you might need another go where you filter out all high frequencies, just leave the bass and add this to your mixdown.
If you use Audacity, there is a plugin that does exactly this process for you. So you can just download the software and throw the plugin at the song. Just mark everything (Cmd+A) and go to "Effect"->"Vocal Removal (for center-panned vocals)". You won't have as much manual control, but if you never did this before, that might be a good thing.
You will notice that it probably sounds rather crappy...
The room reverb of the voice is not centered and will still be audible, and you are probably also messing with the other instruments. But that is as far as you can take it without spending money on a karaoke version.
Hope that helps. If you have questions on the video shooting part, you might get more answers in this particular forum. One thing up front though: Before you export your recorded audio file to make the video to, be sure to add a few click or beep sounds in the beginning. That will make it much easier to line up the video and audio in post production.