If you've downloaded or had the Android 2.3.6 update pushed to your AT&T, T-Mobile, or unlocked Nexus S recently without issue, consider yourself lucky. None of this applies to the Nexus S 4G on the Sprint network.
While we reported that the update was breaking Wi-Fi and USB tethering initially, it seems something much, much worse is happening to some users who have received 2.3.6 OTA.
If you check out this Google thread, you'll see a number of poor souls have had all cellular connectivity stripped from their devices after updating. The easiest solution so far? Roll back to Android 2.3.4 (or earlier), which almost inevitably requires a full wipe of the device. Yikes. There's similar threads over at XDA, here and here.
A new radio baseband version was included in the update, and this seems to be the root cause of the aforementioned connection woes. Some savvy folks over at XDA have come up with an alternative solution, but it requires a bit of hackery.
By rolling your phone back to an older radio baseband version (instead of the entire OS), you can save yourself from rolling back the OS or conducting a full wipe. However, you'll need to follow the instructions for "Method 2" over on this XDA thread very, very carefully. To do this, you need to figure out which model your Nexus S is (I9023 and I9020T are T-Mobile, I9020A is AT&T), backup your EFS folder, and then download one of the older radios and flash it via ADB (included in the files). For AT&T and GSM Unlocked phones, the UCKD1 radio is advisable. For T-Mobile, KD1 should do the trick. Other radios may work as well.
Once you've flashed, if you have no 3G connection, you'll have to reset it manually using the "Retrieve 3G Data Connection" fix located in the same XDA thread. Read everything carefully, and if you're not sure you can manage doing this: don't. Missteps could result in a bricked phone.
Again, the alternative option is go into ClockworkMod, make a nandroid backup, then wipe the whole phone and reflash it to something like CyanogenMod or an older Nexus S image. We recommend the former. Good luck.