Whether the phone is tied to Verizon, T-Mobile, or any other carrier - it's still an iPhone 4. They're all made the same.
Make sure your phone is turned off first.
On the right hand side of the device, about an inch up - there's a small hole. This small hole is the SIM card release latch. Find yourself a paperclip and straighten it out. Stick it in the hole and push gently but firmly. A small tray should pop out from the side just above the hole. In the tray you'll find the SIM card and a small clip that holds it in place in the tray.
Once removed, you can change the SIM card and re-insert it.
Keep in mind though that this does not mean you can use a different network - the phone would need to be unlocked first. You would still be tied to Verizon.