Unlock the Bootloader

Once into the bootloader, you'll need to unlock it. THIS WILL WIPE ALL OF THE DATA ON THE NEXUS PHONE. So have all of your goodies backed up before you do this, or better yet, make this the first thing you do when you take your Nexus out of the box.

$ fastboot oem unlock

Once you've issued the command, the phone should prompt you as to whether or not to proceed. Once you've chosen to do so, your phone will now be unlocked, and you can flash it with a custom recovery image.