  We investigate the idea that decoherence is connected with the storage of
information about the decohering system somewhere in the universe. The known
connection between decoherence of histories and the existence of records is
extended from the case of pure initial states to mixed states. Records may
still exist but are necessarily imperfect. We formulate an
information-theoretic conjecture about decoherence due to an environment: the
number of bits required to describe a set of decoherent histories is
approximately equal to the number of bits of information thrown away to the
environment in the coarse-graining process. This idea is verified in a simple
model consisting of a particle coupled to an environment that can store only
one bit of information. We explore the decoherence and information storage in
the quantum Brownian motion model. It is shown that the variables that the
environment naturally measures and stores information about are the Fourier
components of the function $x(t)$ (describing the particle trajectory). The
records storing the information about the Fourier modes are the positions and
momenta of the environmental oscillators at the final time. Decoherence is
possible even if there is only one oscillator in the environment. The
information count of the histories and records in the environment add up
according to our conjecture. These results give quantitative content to the
idea that decoherence is related to ``information lost''.
