When you sync your iPhone, iTunes backs up your files in:
Mac: ~/Library/Application Support/MobileSync/Backup/
Windows XP: \Documents and Settings\(username)\Application Data\Apple Computer\MobileSync\Backup\
Windows Vista and Windows 7: \Users\(username)\AppData\Roaming\Apple Computer\MobileSync\Backup\
Apple has some more information about iPhone and iTouch backups here
It doesn't mention voicemail, but voicemail files are indeed included.