As best I can recall, I think that Verizon blocks it and prohibits it, which would fit with their general policies of crippling phone features and capabilities, plus I know of cases where they have abruptly canceled accounts where they felt their so-called “unlimited data” had been exceeded. Sprint, I don’t know about. iphone, no.
The G1, yes, plus a couple more Android OS phones are coming to T-Mobile in the coming months, so there will be additional options there. If you want more info for tethering the G1, which would also apply to other upcoming Android phones, I can provide that, but the above is all the info I have for you on other carriers and phones with regard to tethering. Google search the phones and/or carriers you are interested in along with “tethering” and I’m sure some info will pop up in the results.