Why is it valid to take the partial trace to describe a subsystem? In derivations of decoherence, there eventually comes a point when we are asked to take the partial trace over the environment. Why should this be valid for an entangled system? Why should taking the partial trace give the correct description of the system? Taking the partial trace turns a pure density matrix into a mixed density matrix, but a pure state is always a pure state. In what sense can the reduced mixed density matrix be assigned probabilities?
 A: Practically speaking, without the tracing operation you wouldn't have any way of describing an entangled system. You probably already know that if you have a Bell-like entangled state of two systems, you can't write down a state vector to describe either system independently -- only for the combined system does a state vector exist. The natural extension of an object that describes a system when it is entangled is the reduced density matrix (with a trace in it) with its interpretation as a probability distribution.
But it's even more obvious why you should use a trace when you realize that the analog of the reduced density matrix in mathematics/statistics is the marginal probability. The very idea of writing down a description for a system when you don't care about what the other system does is captured in the marginal distribution and the associated summing over all possible states of the other system/environment (the trace). There's just no other consistent way of thinking about writing down the description for an entangled system.
A: Dear Gunther, a partial trace contains all the information about possible predictions made for the subsystem that you haven't traced over. It's trivial to see why.
First, take the whole system A+B. They may be entangled but we're only interested in future measurements of A. If the description for A+B is a pure state $|\psi\rangle$, then define 
$$\rho = |\psi\rangle \langle \psi |$$
The expectation values of the operator $P$ in $|\psi\rangle$ are trivially equal to  ${\rm Tr}\,(\rho P)$, do you see why?
Now, $\rho$, the density matrix, is an operator acting on the total Hilbert space which is the tensor product $H_A\otimes H_B$. And operators $L$ that only act on the system $A$ have the form
$$ L = L_A \otimes {\bf 1} $$
They're just tensor product of an operator acting on $H_A$ only and the identity operator acting on the Hilbert space $H_B$. Do you understand why? Then it's obvious that
$$ {\rm Tr} \,( \rho L) = {\rm Tr}_{ab} \,( \rho (L_A\otimes {\bf 1}))   $$
where $ab$ indicates that the tracing goes over indices corresponding to the basis of $H_A$ as well as those of $H_B$. You can see that the tracing over both types of the indices may be made one by one. You may first trace over the $b$-type indices. However, only $\rho$ depends on $b$-type indices while $L_A$ doesn't and ${\bf 1}$ doesn't make a difference. So
$$ {\rm Tr} \,( \rho L) = {\rm Tr}_{a} {\rm Tr}_{b} \,( \rho (L_A\otimes {\bf 1}))   $$
But $L_A$ doesn't contain any $b$-type indices, so it's a constant that may be pulled in front of the trace over $b$-type indices:
$$ {\rm Tr} \,( \rho L) = {\rm Tr}_{a} L_A {\rm Tr}_{b} \,( \rho  {\bf 1})  = {\rm Tr}_a L_A \rho_{\rm traced\,over\,b}  $$
So the trace over $b$ may be made first and the reduced density matrix may then be traced to find properties of the observables linked to the subsystem A.
The fact that this reduction must be possible if you only want to predict A should be intuitive. In classical physics, you also don't have to know another subsystem to write down probabilities of different properties of A - despite the fact that A,B may be correlated. You just integrate over all possible positions and momenta of B. The tracing is the exact quantum analogy of the integration over $x_B,p_B$.
For example, if you have an EPR experiment, A and B may be 100% correlated. But if you only measure A, you won't see the correlation because you don't have any results from B. So you will see that 50% of the photons on the A side are left-handed and 50% are right-handed: the density matrix will be proportional to the unit matrix (times one half) even though the original state for both A,B was pure - but entangled.
