Depends which phone you switch to in the interim. Unless it's another iphone, then nope, at least on Verizon. If you want to save the voicemails you'll have to wait to sell the current iphone until you activate the new one.
As long as you RESTORE FROM BACKUP on your new iPhone then yes, your voicemails will be there. If you backup your phone to iTunes, you can use a program that lets you open iPhone backups and save them to your computer
)