BE stores the keys in Backup Exec Database. A copy of BEDB will be saved to DATA folder in BE installation directory as part of daily maintenance (if enabled).
As long as your new media server (after installing 64-bit OS) has same user accounts and part of same domain as current media server, you can use the copy of current database to get all the configuration back on new installation. This keeps existing encryption keys intact on new setup also. If any change in domain or user accounts, you can create the encryption keys again on new setup using the exact pass phrases used while creating encryption keys in current setup.
Take a backup of DATA and catalogs folders from BE installation directory.
Have a look at this TN for step-by-step migration procedure: http://www.symantec.com/docs/TECH67768
Thanks!