As far as I know it depends on the phone. it has to have DUN enabled and (at least with ATT) you must have a network plan.

When i was in the ATT store i tried out connecting to phones and the net until i found the cheapest one that worked. So if i were you I'd make a trip to a verizon store (preferably not on a weekend or at a mall island store) and test out the phones on display.