Maybe it helps a little to look at how different physical systems combine in classical physics, and then in the quantum realm. First, you seem to balk at the possibility to describe two physical systems using a single mathematical object. But this is done in classical physics, as well: let's consider a classical, discrete system that can be in one of two different states, let's call them R and L. You can envision this system as being a box divided in two, with a ball in it that can either be in its right or left side. A measurement is an operation in which you open the box, and check in what half the ball is found.
Now consider having two 'copies' of this box. These can be situated anywhere---they can sit right next to one another, or one can be in Princeton, the other on Titan; it doesn't matter. What matters is that we can describe the two boxes by one mathematical object, its state S, which can take on the values RR, RL, LR, and LL. A value of S of RR means that you'll find the ball in both boxes in the right half, and so on. Clearly, nothing untowards is implied by this unified description.
Now let's look at the notion of correlations. If, for some reason, only a limited number of states are accessible in practise, then the two boxes are correlated. Let's assume that only the states LL or RR can occur---perhaps because the boxes are manufactured together, and whenever the ball is in the left half in the first box, it'll also be put in the left half for the second box, and similarly for RR. Then, you can instantly gain knowledge about one box by examining the other: if you open the box in Princeton, find the state R, then, because you know that the state of both boxes is RR, you instantly will know the state of the box on Titan is R, as well.
Now, this is all well and good for the classical world, but it won't do in the quantum realm. To take account of quantum physics, we must introduce a principle which has no analogue in classical physics: the so-called superposition principle. What this means is basically, that for every states a system can be in, the linear sum of these states is again a state the system can be in. Now, this is clearly pretty strange classically: me sitting down and me sitting up are perfectly legitimate states to be in; but me somehow doing both is simply unintelligible. Not so in quantum physics; or, with intelligibility being regularly questioned, at least we can subsume that the superposition principle is foisted upon us by experimental results.
But then the story told above acquires a new twist, one which can't be classically understood: just as for any box, with the possibility of being in the states L and R comes the possibility of being in the state L + R, for the system of both boxes, we gain the possibility of it being in states like, for instance, LL + RR. But what does such a state mean?
Well, here we come into trouble with interpretation. Basically, while a box can be in a state L + R, whenever we check experimentally, we find it in either the state L or R, with a probability that is derived from the formalism in a way which I have not bothered to introduce; only when it is either in the state L or R do we find it in those states with certainty. However, after we have found either L or R, if we check again, we will find an answer that agrees with the first one with certainty. We then say that the wave function has collapsed to a definite value.
Now, in the case of a state like LL + RR, what happens is the following: if we check one box (for convenience, the one in Princeton), and we find it, say, in state L, then we know that, if we check again, we must find it again in the state L. But if the state of the total system were still LL + RR, then there would always be the possibility of finding it in the state R. So, this can't be the right state anymore; in fact, the total state must now be LL. But then, we instantaneously know that the state of the box on Titan must now be L, as well! And this despite the fact that before we checked the Princeton box, neither it nor the Titan box could have been said to be in any definite state. Checking the box in Princeton has 'forced' the box on Titan to assume a definite state, as well: this is one of the characteristics of an entangled state. Entanglement, then, is basically correlation + superposition.
From this point of view, it's also clear why you can't do things like use entanglement to send superluminal signals: you can't decide which state the boxes collapse to; in fact, it is just as impossible as in the classical case, when you can merely discover the state in which the two boxes are. Thus, there is no information transferred across an entangled pair; in this sense, while maybe not with the spirit, quantum theory is still compatible with the letter of special relativity.
---------------------
(Sorry for the length; I find that phenomena this unintuitive are better over- than underexplained. I hope this wasn't too kindergarten.)
