Voicemail is saved on Verizon's server, so unless you change your phone number, your voicemail will be available after changing phones.
The only exception is moving to or from an iPhone - it uses a different system. If iPhones are not involved, or you move from one iPhone to another, messages should be intact.
