I believe the possibility mostly depends on your phone capabilities (well, the phone software).
For example, my BlackBerry (with QNX) has no problem, creates a WIFI access point and works as a gateway.
I used to have Samsung with Android, it was telling me that tethering is not allowed, then I've installed an app which did the trick.