To disable OnStar, you simply unplug the antenna. After a while, the transmitter will likely blow-up (because of SWR too high cause by the transmitter "pushing" into a non-existant antenna at full power) and, in the mean time, it won't connect to the cellular network 90% of the time because the signal will be too low.
OnStar DOES use the cellular phone network so, if your phone have no reception, it is likely OnStar won't work, unless they are on a competitor's network who happen to have a cell tower closer than your cell phone provider's. I think OnStar use CDMA so, Bell and Telus in Canada.
OnStar can't be removed on newer models. On older ones, (the ones with big cell phone antenna) the cellular module and GPS were separate from the car's electronics but nowadays, they are integrated to other components. The removing of the antenna wire for the cell phone and gps is still the best and simpler way to go.