The particle does not know anything. The information is what we (physicists, experimentalists) can communicate to someone else.
Ask yourself: what can $A$ do, sharing an EPR pair with $B$, to tell something (let's say $0$ or $1$) to his friend $B$ after they have left each other (but still sharing at a distance the EPR pair), in a superluminal way?
You will understand that the answer is "nothing", and that the EPR pair is for this purpose as helpful as sharing a pair of gloves ($A$ has either the left one or the right one, B has the other and none of them knows who has what when they leave each other.).
From what concerns locality the EPR pair and the gloves are the same, and so you will agree with me (since none has ever published a superluminal information transfer protocol based on a pair of gloves) that entanglement is fine with relativity.
The difference between EPR and gloves is just a quantitative one, the EPR allows a bit more correlation (see Bell Inequalities) and since Nature allows that too (see Alain Aspect experiment) the EPR is much more realistic than a description based on hidden variable (i.e. gloves-like situation).
Just another comment, that I've found very useful, do not think of the wavefunction as "something that is really there" so that an istantaneous collapse of it may appear as violation of locality (when $B$ measure his qubit he make collapse the entire wavefunction...). The wavefunction is a mathematical tool to predict probabilities, the probabilities are the only thing that are "really there" since we actually see them in experiments. And you will notice, $B$ cannot change the probabilities for $A$'s measurement.
See also the reference frame blog for very nice posts about this stuff.
EDIT -
I think the point of our disagreement is that you stick to a POV where the particle "chooses" a state after being measured and so it appears to you that the two particles have to exchange "information" in order to give coherent (correlated) answer when measured. Therefore you see a substantial difference from the classical case of gloves, where they already knew what they where (though the glove carriers didn't). This is what I think you think, but correct me if I am wrong.
Now, It seems to me that such a POV is a vestige of the so called “realism” of classical mechanics, i.e. That any physical observable has a definite value at any time. This pone a separation to what we, the experimenters, know and what the particle knows. So, for the case of the gloves, we do not know what glove it is, but the “glove” knows itself and so there is no FTL communication between them notwithstanding the same space-like perfect correlation (quoting your last comment).
In QM realism of course does not exists (as the Bell inequalities have shown) and so the above considerations have to be changed: No one, not even “the particle”, knows what will be the outcome of a measurement.
Such a shift of paradigm requires to fix some terminology and boundaries on what is “physical” and what is not.
The physical content of QM are the probabilities of measurement, that we , the experimenters, can predict and observe, nothing else.
This is an idea deeply radicated in any QM theory we have about the world.
Any different calculations or object that lead to the same probabilities may be thought as “redundant”, “not physical”. For example in QFT the fact that there is no privileged inertial reference frame is encoded in the fact that performing a Poincarè transformation correspond to act on states with an (anti-)unitary operator, that leaves unchanged the probabilities.
To sum up: "we" are the experimenters, of a given QM system we can only predict and observe probabilities and nothing else, and causality must agree with this fact (and nothing else).
Having said this, I invite you to re-think about the EPR experience from this POV, where probabilities play the central role.
The only thing that appear as “non-local” is that when A measures his particle he istantly changes the total wave-function of the two particles, from $|\mathrm{EPR}\rangle$ to $|0\rangle|1\rangle$ (if $A$ obtains $0$, $|\mathrm{EPR}\rangle$ is the usual entangled pair). It appears as non-local since the total wave-function involves both $A$'s and $B$'s particles and they are space-like separated.
But the wave-function is not the true physical content of QM, only probabilities are. And $A$ cannot change any of $B$'s observed probabilities, so in no way $A$ can change the physics that $B$ will experience.