I just installed CyanogenMod on my Galaxy Nexus phone. There is an official guide; here is my summary of what you need to do.

Backup your data

The process will reset your phone, so you need to back up all your data. An useful open-source program to take care of (part of) this is Slight backup.

Retrieve fastboot

Follow these instructions to install fastboot. I'm not sure that this was entirely straightforward, but I did this long ago so I'm not really sure. fastboot is now packaged for Debian so it is much simpler to install: apt-get install android-tools-fastboot.

Unlock the bootloader

Power down the device, and press the power, volume up and volume down buttons simultaneously for a few seconds. You will thus reach the bootloader. Connect the USB cable and run fastboot oem unlock, and confirm. This will reset the device and unlock the bootloader.

Retrieve and run ClockworkMod

I trust the official guide to have an up-to-date ClockworkMod download link. This being said, you don't need to keep ClockworkMod on your device: you can just boot it as needed. To do so, get to the bootloader like in the previous section, and run fastboot boot CLOCKWORK where CLOCKWORK is the ClockworkMod image file.

Perform a backup

Use ClockworkMod to back up the device before installing anything else, and use adb to retrieve the backup to your computer.

Format all partitions

This is an important step missing from the official guide: you should format /cache, /system and /data before installing CyanogenMod. Otherwise, in my case, CyanogenMod was stuck at the boot animation and adb logcat seemed to suggest that it had to do with a NullPointerException while reading the existing settings.

Retrieve CyanogenMod

Download a CyanogenMod image from this page. I first thought I'd go with a stable version, but I picked the latest nightly as of this writing (cm-10-20120923-NIGHTLY-maguro.zip) and had no problems with it yet.

Install CyanogenMod

Use adb to push the downloaded image to the sdcard folder on the device, and install the image using ClockworkMod.