Here's how I have come to think of it: When you create the two opposite-spin particles and send them to opposite ends of the galaxy, they exist in a superposition of states which follows QM probabilities. The spins are anti-aligned in all of these possible states , but pointing in a different direction in each state. When one person observes his/her particle, you can imagine it's like they are 'masking out' many of the possible states, leaving just one of the possible "universes". But no matter which "universe" gets masked out, in the "surviving universe" the spins are going to be anti-aligned.
This is a lot like the 'hidden variable' picture where the spins were pre-decided and put into boxes, and when person A opened her box and saw "up" she knew that the other person must have the "down" spin. The difference is that QM probabilities are not consistent with the probabilities you would get from such a boxing procedure (in particular when the observers measure the spin at different angles). But conceptually, opening the box and realizing that you have the "up" spin and therefore the other person has down is a lot like doing a spin measurement and masking out many of the superpositions, and concluding that the other person must have the opposite spin from what you measured.