I don't understand how a Trezor is considered cold storage if you can lose it, and then recover your keys through their recovery seed and another Trezor.
Where are the keys coming from?
Where are they being stored?
It is considered cold storage because the private keys are never exposed to an online device which can steal them.
The private keys are stored on the Trezor itself. They can never leave the Trezor, even when it is plugged into a computer. Thus they are never exposed to something which is connected to the internet that is able to steal the private keys.
The recovery seed is a BIP 39 mnemonic. This encodes a BIP 32 seed which is then used to generate all of your private keys. The Trezor actually only stores the BIP 32 seed and generates all other private keys when they are needed. Restoring a Trezor with the recovery seed (aka BIP 39 mnemonic) just tells Trezor what the BIP 32 seed should be.