i used koush's method, but before running any commands in adb or fastboot run "sudo su" (without the quotes of course) to change to root. this is where i got caught up - running the commands without being root will probably lead to you not having permission to do anything with the device. once i figured that out, it was smooth sailing.
http://androidforums.com/verizon-ga...49-how-root-vzw-lte-samsung-galaxy-nexus.html
http://androidforums.com/verizon-ga...w-unlock-bootloader-galaxy-nexus-verizon.html
from there, just do exactly what the guide tells you and it should be done within minutes...literally. the only thing i did slightly differently was in unlocking the bootloader - i connected to the computer while the phone was on, then opened terminal, navigated to platform-tools, and ran ./adb devices. i did this because i'm paranoid and wanted to make sure adb was working before i tried to go into fastboot. this is where i saw the "??????????????????? no permissions" thing...so, from there, after a half hour or so of searching and trying to figure it out, i finally found the answer:
sudo su (enter your password when prompted)
./adb devices
when you run ./adb devices after switching to root, you should now see that adb can see your device is connected....
./adb reboot bootloader
./fastboot oem unlock (after the phone boots into the bootloader, of course)
follow the guide/video from there
also, watch the video once before you start...even though it's done on a windows pc, it's still helpful for following how the whole procedure works. it's much easier on ubuntu because you don't have to mess with the drivers...
don't forget to exit out once everything is done, so you're not sitting there in the terminal as root for longer than you need to be.