Verizon uses CDMA, so they do not have a SIM card. However, CDMA phones can be unlocked. Here's link to a good post discussing it:
How-to: Unlocking a CDMA Phone...
I know that Verizon instituted a policy where you operate non Verizon CDMA phones on the Verizon network so my guess is that you'll still be able to get an unlocked CDMA version of the phone that would work on Verizon. However, I don't think that Sprint (the other US carrier using CDMA) allows unlocked phones on their network, so it's not like an unlocked CDMA does much for you in the US.
Sorry I don't have more details on the Verizon policy, I just remember reading about it and hearing about it from a tech at a Verizon store.
Also, given that Verizon does not reduce the cost of their plans when you get a plan without a contract, it would not be cheaper to get an unsubsidized Nexus One and use it on Verizon.