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.
Not sure whether this a common thing, but my cellular provider shrinks the images when I browse the Internet (to reduce the bandwith).
I've described it in this thread. So you don't notice it on your phone screen, but it becomes obvious on a large screen with tethering.