The answers and comments here are good, but I think that it's worth tidying it all up a bit. The question is broad, and this is exactly expressed in the answers. There are multiple questions here. Before I begin, I note that when we talk about the keys not being "independent", we need to define what we mean. I am only going to relate to the keys being the same. If you let the keys be related (e.g., one is the inverse of the other), then it's easy to come up with counter-examples showing nothing is secure. However, in reality we are interested in the same key versus independent keys. We will start with these three questions:
- Is double-encryption necessarily secure when the algorithm and keys are the same?
- Is double-encryption necessarily secure when the algorithm is the same but the keys are independent?
- Is double-encryption necessarily secure when the algorithms are different but the keys are the same?
What attacks are we considering as well? If we only consider eavesdropping then it's different to the case that we consider chosen-plaintext attacks. We also need to ask whether we are considering the case that both algorithms are secure or not. (Of course, if they are both secure, then why bother double encrypting. So we'll consider the case that it's only guaranteed that one is secure later.)
Let's start by answering the above three questions:
- When double encrypting with the same algorithm and the same key, and when the scheme is secure under chosen-plaintext attacks, it is easy to see that security is preserved. This is easy to prove: a CPA attacker can double encrypt by itself by querying the ciphertext back to the oracle. Therefore, if one can break the double encryption then one can break the single encryption. However, if the scheme is only secure in the presence of an eavesdropping adversary, then double encryption can break (for security, define that the adversary outputs two vectors of plaintexts, gets their encryption, and needs to determine which vector was encrypted). In particular, take any eavesdropping-secure encryption scheme and modify it so that an encryption of an encryption of 0 outputs the secret key. This will still be secure in the presence of eavesdropping adversaries (easy to prove; will leave it to you). However, this will be completely broken when using double encryption.
- When encrypting with the same algorithm and independent keys, it's easy to prove that security is preserved. The reduction can generate the second key itself. So, this is secure even if the scheme is only secure in the presence of eavesdropping adversaries.
- When encrypting with different algorithms and the same key, you're in big trouble. This should be obvious since you are never allowed to reuse keys for different schemes. I'll leave this again to you to come up with a concrete counter-example (just make sure that both schemes are secure).
A more interesting/important question is whether double encryption is secure when one of the schemes may be insecure. In general, constructing a scheme that is secure from a number of schemes where only some of them are secure has many advantages. The first construction of HMAC used a combination of SHA1 and MD5 for this reason. Formally, we call such constructions robust combiners. Regarding double encryption, this is the cascade research here.