My phone was stolen and they deleted my contacts. They must be backed up somewhere? How can I restore them to my new Galaxy? Everything else came back.
Did you select an online/synced account as the location for your contacts?
You can simply login to your former account and synchronize the contacts to your new device.
Did you select SIM card as the location?
I hope you've got that card. Simply put it in your device and your contacts are back. Move them to an online account or do whatever you want with them.
Did you select phone or device as the location?
Well, there are your contacts now. And they won't leave your device any time soon.
Some manufacturers offer you to sync those contacts to their services anyways so maybe you can login to that account and restore your contacts.