There is no ideal way that I'm aware of. Most of the time vocals are aimed straight down the middle of the stereo field, so isolating this in the track can help....but this is very much dependent on how the song was recorded. Even then it will only quieten them not always cut them completely...There is a plugin that you can use that attempts this called Vocalzap..
Other then that, the only other way would be to play with eq's, to cut out as much as possible. Bare in mind that by doing this you could loose other parts of the song too.
Maybe someone else can offer a better solution, but I don't know of one.
When you're hired to do this kind of work the label will send you a copy of the masters... the vocal will be on its own track and it will be easy. If you're not in the situation where the label is sending you remix work... hire a singer to re-sing the parts.
The most effective way I've found of doing it is to invert the phase on one channel of the track and then sum the entire track to mono. This kinda works, unless you have vocal parts that aren't panned center. Since you are basically removing everything that is center panned, some songs will sound better with this process than others
But, like Fletcher said, the proper way to go about getting a vocal-less track is to get it straight from the label.
Probably illegally by people that hacked into Rock Band files or insiders that release the tracks without permission. Think about it, who would let out their money making tracks for free, so that anyone could change them?
There were a lot of old recordings that had the vocals on one side and the band on the other, like the early Beatles, you could hunt out some of these. There are some great gating techniques, eq techniques and as said before use out of phase tricks.
I always remember the track "Why Does My Heart Feel So Bad" from Moby, if you listen to the vocal your can hear the old music track in the background and the gate closing. Moby in an interview said that he could get rid of more of the back ground but he liked the sound with the slight music and the gates closing better. On one of my old band tracks years ago I lifted a famous singers vocal and sampled the line as a harmony (name not given to protect form being sued, however the band is still poor so there is nothing to sue for), we also triggered this at live shows, the original record had the vocal on both left and right, but when I checked the left and right one side separately mostly had organ and vocal, the organ in with the vocal actually made it more interesting. So what I am saying is you have to get inventive.