take your old phone and your new one to the verizon store and they should be able to transfer everything from there
edit: they should be able to transfer MOST of it. It seems hit or miss sometimes. Ive done it with phones where everything transferred fine, but when I transferred my contacts from my env touch to my droid, some contacts were missing