Keys are stored within AWS Key Management Service, which relies on Hardware Security Appliances (a dedicated tamper-proof hardware appliance just for storing secrets). For EBS, encryption works like this (I imagine RDS will work similarly):
The basic steps to encrypt data being written to an EBS volume are:
1. Amazon EBS obtains an encrypted volume key under a customer master key through AWS KMS, and stores the encrypted key with the volume metadata.
2. When the EBS volume is mounted, the encrypted volume key is retrieved.
3. A call to AWS KMS over SSL is made to decrypt the encrypted volume key. AWS KMS will identify the CMK and make an internal request to an HSA in the fleet to decrypt the volume key, and will return the volume key back to the customer over the SSL session.
4. The volume key is stored in memory and used to encrypt and decrypt all data going to and from the attached EBS volume. Amazon EBS retains the encrypted volume key for later use in case the volume key in memory is no longer available.