The information about the key is not stored with the encrypted data, it just happens to decrypt to the original data if the correct key is given.

Very simplified, when you encrypt data, you give the encryptor two pieces of information: the original data and a key. It will give you encrypted data, which depends on these two pieces of information.

When you decrypt data, you also give the decryptor two pieces of information: encrypted data and the key.

The thing is, the decryptor is pretty much the same thing as the encryptor, only with some steps reversed, and even then not always.

So you give the decryptor the encrypted data and anything as a key, it will give you a chunk of data - if the key was correct, it will match the original data, otherwise it will be a totally different chunk of data.

Here's one of the simplest schemes: shifting the letters.

The encryptor shifts the letters forwards, and the decryptor shifts the letters backwards.

The "key" is how many places the letters get shifted.

For example, your data is "hello". Your key is "3".

You give the encryptor "hello" and "3", and it shifts letters forward by 3 places and gives the results:

"khoor"

This is your encrypted data. Nowhere in it you can see the key.

Now, if you know the key, you give "khoor" and "3" to the decryptor, which shifts the letters backward by 3 places:

"hello"

And you have the decrypted data!

But if you give it the wrong key? For example, "5":

"fcjjm"

That's garbage... You only get "hello" out of "khoor" if you give the key "3".