How can the quantum state of the universe decohere Decoherence explains how a classical state appears once quantum information in a quantum state leaks out. But presumably that environment has its own quantum state which then leaks out to a larger environment.
Does this mean that decoherence can only be understood locally, and not globally? For example if the entire universe is encoded in a quantum state how can it decohere?
 A: As mentioned in the comments, there's no guarantee that the quantum state of the universe is a concept that even makes sense.
Assuming the universe is describable by quantum mechanics, and assuming it's a quantum system with nothing to interact with ever, and (most importantly) assuming all interactions and evolutions happening inside are unitary (even though there's no guarantee any of these assumptions are the least bit plausible); then no, it probably can't decohere. 
Decoherence, as in a pure state becoming mixed, can only happen in unitary QM when the system entangles with something else and you insist on looking only at the system. It's easy to see this case is excluded by the assumptions. 
Note however, that the unitary assumption is very much not plausible - it is incompatible with measurement collapse, and let's not even get started on relativity. And without it the answer would be: yeah sure, whatever you want. =)
A: I think that one should be grounded in real life physics.
All experiments have measurement errors and all experiments measuring quantum states have measurement errors. These may come from the instruments but they may also be effective measurement errors because of the enormous order of magnitude  differences within the various measures of the quantum states.
For example in simple potential problems gravity should be taken into account in solving Schrodinger's equation, but the difference in the effect  between an electric potential and the gravitational potential allows us, within our measurement capabilities to ignore g and get correct verifiable results.
Decoherence is best seen in the matrix format where the overlap of the pure states fills the off diagonal elements of the density matrix. In a completely decohered state there would only be density matrix elements on the diagonal, the expectation value of each pure state, that can build up the classical view.
Now suppose ( a hypothesis) the universe could really be described by such a density matrix completely, all the elements of the matrix filled with accuracy. There will be enormous  order of magnitude differences , making practically all non diagonal elements within errors zero with respect to the diagonal ones. On the one hand the small gravitational constant, on the other the distances between matter conglomerates, on a third the small value of h ( the Planck constant) all will guarantee that decoherence is a measurable reality, except for localized clusters within the accuracies of h .
A: An interesting state (thermofield state) is : 
$$|\psi\rangle = \sum_n e^{- \frac{\beta}{2} E_n}|E_n\rangle_1|E_n\rangle_2$$
where $1$ and $2$ are regions separated by a space-like interval.
When you make a measurement in the region $1$, you will have to perform a partial trace on $2$, and you get a thermal state $\rho_1 = e^{-\beta E}$
So, even if the evolution of the universe is unitary (for instance with an entangled state), practically measurements are done locally
