I also had this problem since I upgraded my 3GS on Thursday. I did a full restore from a backup, and my internet still wasn't working. Like others, my WiFi was working though. From information I gleaned, it's either corrupt APN settings, or I think in my case (I checked and my APN settings were blank), that updating it just deleted them altogether.
On your phone tap Settings > General > Network > Cellular Data Network.
If it's all blank like mine, you need to find out your carriers APN settings and input them. Restart the phone, and it should work.
On your phone tap Settings > General > Network > Cellular Data Network.
If it's all blank like mine, you need to find out your carriers APN settings and input them. Restart the phone, and it should work.