It can be done with varying levels of effectiveness, the less amount of non-vocal, the better.
eg. If it's just voice and guitar, that should be easy, the more instrumentation, the harder it will be to separate unless you can get hold of the original multitrack - which is unlikely. An exception would be a mix where the vocals are hard-panned to one side of the stereo (eg. Buffalo Gals by Malcolm McLaren).
You will need some music editing software that does "noise reduction" though.
I use Cool Edit Pro (now known as Adobe Audition).
If you've made it this far into my response without going "hrrrrrrmmm - soddit" let me know and I'll explain further :-)