I don't know if the iPhone 4 has a direct method to enter a permanent unlock code on the phone (other than via jailbreaking), but in the past, the iPhone could be unlocked via your service provider sending a request for your IMEI to be added to a list on Apple's servers. Then the next time you connected your iPhone to iTunes, you'd receive a carrier update which would permanently apply the unlock.
I'm guessing Verizon will have this capability. Unless the requirements have changed, this is the way to do it:
VERIZON SIM UNLOCK TUTORIAL
1. Make sure your phone line has been active and had no late payment history for at least six months. If it hasn't, VZW will likely not unlock your SIM (although sometimes a rep will make an exception.)
2. Call VZW Global Support at 1-800-711-8300 and ask the representative for your phone's SIM unlock code (or in the iPhone's case, to add your phone's IMEI to the Apple unlocked phone whitelist.)
FYI: You will not be able to use this device on AT&T or T-Mobile, even if SIM unlocked. Verizon restricts the US GSM bands on their GSM-enabled phones.