The classic example of quantum entanglement is called the EPR paradox. In a simplified version of this case, consider a particle with quantum spin 0 that decays into two new particles, Particle A and Particle B. Particle A and Particle B head off in opposite directions. However, the original particle had a quantum spin of 0. Each of the new particles has a quantum spin of 1/2, but because they have to add up to 0, one is +1/2 and one is -1/2.
This relationship means that the two particles are entangled. When you measure the spin of Particle A, that measurement has an impact on the possible results you could get when measuring the spin of Particle B. And this isn't just an interesting theoretical prediction, but has been verified experimentally through tests of Bell's Theorem.
One important thing to remember is that in quantum physics, the original uncertainty about the particle's quantum state isn't just a lack of knowledge. A fundamental property of quantum theory is that prior to the act of measurement, the particle really doesn't have a definite state, but is in a superposition of all possible states. This is best modeled by the classic quantum physics thought experiment, Schroedinger's Cat, where a quantum mechanics approach results in an unobserved cat that is both alive and dead simultaneously.
One way of interpreting things is to consider the entire universe as one single wavefunction. In this representation, this "wavefunction of the universe" would contain a term that defines the quantum state of each and every particle. It is this approach that leaves open the door for claims that "everything is connected," which often gets manipulated (either intentionally or through honest confusion) to end up with things like the physics errors in The Secret.
Though this interpretation does mean that the quantum state of every particle in the universe affects the wavefunction of every other particle, it does so in a way that is only mathematical. There is really no sort of experiment which could ever - even in principle - discover the effect in one place showing up in another location.
The reason that this is classified as a paradox is that it seemingly involves communication between the two particles at speeds greater than the speed of light, which is a conflict with Einstein's theory of relativity.
The paradox was the focal point of a heated debate between Albert Einstein and Niels Bohr. Einstein was never comfortable with the quantum mechanics being developed by Bohr and his colleagues (based, ironically, on work started by Einstein). Together with his colleagues Boris Podolsky and Nathan Rosen, he developed the EPR Paradox as a way of showing that the theory was inconsistent with other known laws of physics. (Boris Podolsky was portrayed by actor Gene Saks as one of Einstein's three comedic sidekicks in the romantic comedy I.Q..) At the time, there was no real way to carry out the experiment, so it was just a thought experiment, or gedankenexperiment.
Several years later, the physicist David Bohm modified the EPR paradox example so that things were a bit clearer. (The original way the paradox was presented was kind of confusing, even to professional physicists.) In the more popular Bohm formulation, an unstable spin 0 particle decays into two different particles, Particle A and Particle B, heading in opposite directions. Because the initial particle had spin 0, the sum of the two new particle spins must equal zero. If Particle A has spin +1/2, then Particle B must have spin -1/2 (and vice versa). Again, according to the Copenhagen interpretation of quantum mechanics, until a measurement is made, neither particle has a definite state. They are both in a superposition of possible states, with an equal probability (in this case) of having positive or negative spin.
There are two key points at work here which make this troubling.
If you measure Particle A, it seems like Particle A's quantum spin gets "set" by the measurement ... but somehow Particle B also instantly "knows" what spin it is supposed to take on. To Einstein, this was a clear violation of the theory of relativity.
No one ever really questioned point 2; the controversy lay entirely with point 1. David Bohm and Albert Einstein supported an alternative approach called "hidden variables theory," which suggested that quantum mechanics was incomplete. In this viewpoint, there had to be some aspect of quantum mechanics that wasn't immediately obvious, but which needed to be added into the theory to explain this sort of non-local effect.
As an analogy, consider that you have two envelopes that contain money. You have been told that one of them contains a $5 bill and the other contains a $10 bill. If you open one envelope and it contains a $5 bill, then you know for sure that the other envelope contains the $10 bill.
The problem with this analogy is that quantum mechanics definitely doesn't appear to work this way. In the case of the money, each envelope contains a specific bill, even if I never get around to looking in them.
The uncertainty in quantum mechanics doesn't just represent a lack of our knowledge, but a fundamental lack of definite reality. Until the measurement is made, according to the Copenhagen interpretation, the particles are really in a superposition of all possible states (as in the case of the dead/alive cat in the Schroedinger's Cat thought experiment). While most physicists would have preferred to have a universe with clearer rules, no one could figure out exactly what these "hidden variables" were or how they could be incorporated into the theory in a meaningful way.
Niels Bohr and others defended the standard Copenhagen interpretation of quantum mechanics, which continued to be supported by the experimental evidence. The explanation is that the wavefunction which describes the superposition of possible quantum states exists at all points simultaneously. The spin of Particle A and spin of Particle B are not independent quantities, but are represented by the same term within the quantum physics equations. The instant the measurement on Particle A is made, the entire wavefunction collapses into a single state. In this way, there's no distant communication taking place.
The major nail in the coffin of the hidden variables theory came from the physicist John Stewart Bell, in what is known as Bell's Theorem. He developed a series of inequalities (called Bell inequalities) which represent how measurements of the spin of Particle A and Particle B would distribute if they weren't entangled. In experiment after experiment, the Bell inequalities are violated, meaning that quantum entanglement does seem to take place.
Despite this evidence to the contrary, there are still some proponents of hidden variables theory, though this is mostly among amateur physicists rather than professionals.
Personally, I feel the same way.
The EPR Paradox is not a paradox. It is a rigorously constructed thought experiment, which Einstein, Podolsky and Rosen believed would lead to the overthrow of quantum mechanics when it became clear that real experiments would never verify it. Unfortunately, they were wrong: Quantum Entanglement is real.
Schroedinger's cat is a cat of a different stripe. Frankly, it is not rigorously constructed and a lot of physicists don't see any real issues once you point out the obvious shortcomings. Einstein and Schroedinger actually corresponded over a better version of the paradox which does not involve a cat, but a barrel of dynamite, which, at least in the Copenhagen Interpretation of Quantum mechanics must be partially exploded and partially unexploded until you open the box. It never caught on because nobody cares about a dead physicist who stupidly opens a box containing a mixed superposition barrel of dynamite, just to see if he can project its eigenvector into the right subspace of Hilbert space by inspection, but cats are cute and fluffy.
Removing the cat removes a number of issues, not least of which is that if all that's required is an observer, the cat surely knows if it's alive or dead, which kind of spoils the quantum mechanical surprise when you open the box.
More problematic is the troublesome fact that quantum mechanics requires as one of its axioms that every observable quantity must correspond to a Hermitian operator. Since we don't have a definition of what it means to be "alive" in physics, it's highly unlikely that any such operator even exists. That's a job for biologists, and their definition is suitable for their problem domain, but it's far too "big" to be used in physics any time soon, and is likely to involve more than a single "life operator" anyway.
If there is no such operator, it has no eigenstates either and hence there is no superposition of "live" and "dead" cat states.
Finally, it's been a pretty hot topic of research since the 1980's [although the concept was raised many times in the past in a way that wasn't well articulated] the very notion that there is actually a quantum connection between classical objects [like cats] and quantum mechanical objects [like atoms] in Schroedinger's version of quantum mechanics is far from settled, and that's one of the reasons that in discussing the measurement of quantum systems with classical instrumentation the whole question of quantum coherence and decoherence has become much more interesting.
In response to a two day discussion of the Schroedinger Cat Paradox in the second quantum course in grad school [actually the Measurement Problem in general, which is a much bigger problem, of which Schroedinger's Cat is just an example], one of the students circulated a mimeograph [it's all we had to stand in for the Internet in 1978] mocking the whole thing entitled, Congratulations! You've Created a Machine That Might or Might Not Kill a Cat. Now Get Over It. That pretty much sums up how most physicists I knew felt about Schroedingers G*dd*m cat.
Fortunately, quantum computing in no way relies on the Copenhagen Interpretation or on Schrodinger's cat, whether alive, dead, or in some admixture of the two.