My GSM/HSPA+ variant of the Galaxy Nexus just arrived, and just in time before my trip to Europe. Turns out, the one I bought was a Samsung variant (codename YAKJUXW -- same hardware but different firmware), which gets its updates from Samsung, not Google. This sucks for a variety of reasons. Most notably, if you let the phone update itself, it will get to Android 4.0.2 and then consider itself "up to date".

(If you're buying directly from Google, this won't be an issue for you. If you're buying elsewhere, here's how to fix it.)

There are some reasonable noob instructions for fixing this. In short, you get your phone set up for USB debugging and then you can run adb and fastboot commands from your computer. You download the 4.0.4 image directly from Google's Android images. I grabbed the "takju" image for Android 4.0.4 + Google Wallet. That tarball unpacks and includes a "flash-all.sh" shell script. All you do is first run "adb reboot bootloader" and then that shell script. Here's another good link that describes the process.

This process completely wipes the phone. Needless to say, don't start installing your personal stuff on the phone until you get done with all the upgrading.

Okay, but a phone running 4.0.4 doesn't (yet) automagically update to 4.1.1. Now that AOSP is out, this should be available at the Google link, above, at some point, but it isn't today. Nonetheless, the incremental updates exist. This page has the links. My phone, with 4.0.4, is running the IMM76I build (which you can learn by running "adb pull /system/build.prop" and reading the text in the file). So I downloaded the 147MB zip file labeled "takju JRO03C from IMM76I".

Once you've got this zip file, it's simplest to follow "method 2" (stock recovery, unlocked bootloader) to get it installed. I used adb to push the zip file over to the phone, then "adb reboot bootloader" and "fastboot boot cwm.img" and you're good to go. And it worked!

Lastly, when you do this, you have an unlocked phone, but you don't have root on it. If you want root, then these instructions are overkill but seem correct. The gist is that you push a zip file which has SuperSU in it, and which can be run from the CWM bootloader. The relevant discussion threat for SuperSU is over here, which has a link to the latest version, ready to go.