With studio recordings, it's fairly easy. The vox are usually centered in the mix, and so with a little Audacity you can remove them. I did that once to make a "karaoke mix" of some song my sister-in-law wanted to sing at my other sister-in-law's wedding. It worked pretty well; the vocals were really faint, and the music sounded fine.
With a live recording, besides reducing the vocal presence via EQ, there's really not a whole lot you can do. Even EQ-ing doesn't do a whole lot. You could try the Audacity method, but unless it was mixed right at first, it might not work well.