For each object you upload, a new encryption key is generated, and used to encrypt the object before it's stored to disk.
Having the object stored encrypted means the it's computationally infeasible for someone in possession of the raw data as stored on disk to decrypt it... but, of course, anyone in possession of that key could decrypt it, so the keys have to be stored securely, and in a relatively useless form, and that's done by encrypting them with the master key.
To compromise the stored object, you have to have the specific encryption key for that object... but even if you have it, it's useless since it's also been encrypted. To get it decrypted, or at least have it used on your behalf, you have to have the master key, or have a trust relationship with an entity that controls the master key and can use it on your behalf.
So far, all I've really done is stated the obvious, of course.
The encryption keys, themselves, are tiny, only a few tens of bytes each. When the master key is rotated, the object-specific encryption keys are decrypted with the old key, and re-encrypted with the new key. The new versions are stored, and the old versions are discarded.
Since the keys are small, this is not the massive operation that would be required if the objects themselves were decrypted and re-encrypted... but it's only the per-object encryption keys that are decrypted and re-encrypted when the master key is rotated.
Several analogies could be drawn to an apartment complex, where keys are stored in a common lockbox, where changing the lockbox lock would restrict future access to individual apartments by restricting access to the individual apartment keys by restricting access to the common lockbox. The analogy breaks down, because physical keys are easily copied, among other reasons... but it's apparent, in this illustration, that changing the lockbox lock (relatively simple operation) would be unrelated to changing the lock on one or more apartments (a much more substantial operation).
The bottom line, in this scenario, they create a new secret key to encrypt/decrypt each object you upload, then store that secret key in an encrypted form... periodically, and transparently to you, they change their stored representation of that secret key as a preventative measure.
