The key is not stored with the encrypted data, the encrypted key is. This is part of the header. In short, when the volume is created a random key (the master key) is generated and this random key is encrypted using a key derived from the passphrase, and spread out (using an algorithm called 'afsplit'). This key derivation is designed to take a relatively long time (half a second or so), so it's relatively expensive to try passphrases as an attacker.
By design the system's security depends on the passphrase's quality; a bad passphrase is somewhat protected due to the long time per try, but would fail in the end. The header also contains an independent check to see that the passphrase that was entered has resulted in the correct master key.
The header is not secret but essential to open the volume: it contains all the parameters that have been used when the volume was created, so that (with a correct passphrase) the master key can be recomputed from the header (and this key is used to decrypt the actual file system data). So it's always stored with the data. It is recommended to backup the header (to a separate system, say a USB drive), but this is just to prevent data loss when the header would get corrupted (if a bit is changed, you cannot recompute the correct master key any more).