definitely GreenPois0n...make sure you download the latest version (from the actual site) because the old ones cause problems like FaceTime and MMS not working.
i watched this video tutorial on YouTube under the username "EverythingApplePro" and look for the video named "How To Jailbreak The New Verizon iPhone 4"
i failed about 2-3 times because i couldn't get the phone on "dfu mode". if by any chance you get the recovery logo, all you have to do is hold the home & sleep button till you see the apple logo and then you let go so it boots back to homescreen and you'll get another chance to try it.
goodluck