How do I get my rear wheels off?

You don't say what car, if you have only tried one side, it's possibly LH thread. Which would be righty loosey.

Agreed, this could be a left hand thread, in which case should be only on the drivers side! Of course that could be changed by someone not in the know, but check spinning them both ways!! The torch idea is also good advise!!!