Well, there are a few options, but there are considerable limitations.
First, copyright. The instrumental backing tracks for popular music are usually the property of the producer or record label, so finding these on the internet for free is of questionable legality.
Some labels do provide licensed CDs for exactly the purposes you require (or karaoke, which is relatively likely).
Taking a produced track and "removing" the vocals is technically impossible to do. The master in the recording studio contains the vocals in a separate track that can be easily removed, but once that master is mixed down to stereo, the best you can do is try to identify the frequencies of the voice and pad them with EQ. This is essentially what "remove vocals" in software is doing, but you are of course also taking those frequencies out of the background instrumentals along with the voice.
What is usually the easiest and highest quality option when there are no legal issues is simply to produce one's own backing track. Of course, this takes considerable musical aptitude in various fields, so for those without the ability, you will be limited to what you can get your hands on in terms of licensed instrumental CDs.