Hi Niall,
The encryption keys are not stored in the database (mostly because if the database is compromised we wouldn't want the keys to be easily available). The keys are stored in your file system dataroot instead, specifically a file called encryption_keys.json.
As long as the appropriate key is listed there you can decrypt the content in another environment. We strongly recommend you protect this file, and copying it across environments does introduce more exposure risk (especially a testing environment). I don't recommend it, but that's how it works.
For staging + SAML specifically this is how I'd approach it.
Create a new SAML connection in my staging site to my Identity Provider, specifically for staging (and confirm it works).
Save a copy of the IdP details, including the encrypted certificate for in a SQL script.
Restore the database
Have a script run that overrides both the metadata field and certificate field of my SAML instance, pointing it at the staging connection instead.
That way staging could connect to my SAML IdP, but it technically uses different certificates from production and I'm not sharing encryption keys across two environments so it's safer. If my staging was compromised, my production's still fine.
There's no specific user-to-SAML-instance link, so staging using a different instance doesn't matter.