Verizon‘s Galaxy Nexus which is currently running on Android 4.0.2 is currently getting update to Android 4.0.4 . As according to reports till now only some users are got it in an over-the-air download. We keep hearing “early May” for a release of this update and being May 1. Check your phone immediately and throughout the day to see if you are prompted as well.
More info: Droid Life