How many bytes can the observable universe store? Is the number of states in the Universe countable? 
What framework could be used to answer the question in the title?
 A: Dear J.F. Sebastian, for a few decades, physicists thought that the cosmic microwave background - photons created 350,000 years after the Big Bang that fill the space and currently correspond to thermal radiation at 2.7 Kelvin degrees - carried most of the entropy of the Universe. 
Entropy, denoted $S$, is the physical quantity representing the information that can be carried by the "arrangement of atoms" or other microscopic building blocks. It's the "useless information" that we can't measure in isolation and that is responsible for thermodynamic phenomena. Most of the information cannot be decoded - the question what part of this entropy may be employed as memory in functioning memory chips is an engineering question but it is a small part.
The entropy's unit is "Joule per Kelvin". However, if you divide it by $k$, the Boltzmann's constant, you get a dimensionless number that measures the information in "nats". One bit is equal to $\ln(2)\approx 0.69$ nats, so the dimensionless entropy is approximately the same thing as the number of (useless) bits that the atoms carry.
Microwave background
So what is the entropy of the cosmic microwave background?
The approximate "radius" of the visible Universe is $10^{60}$ Planck lengths, so the volume is $10^{180}$ Planck lengths. However, the CMB temperature is just $10^{-32}$ Planck temperatures or so, which means that the volume has to be counted in units of volume that are $10^{96}$ times larger. We get about $10^{180-96}\approx 10^{85}$ photons in CMB and each of them carries one bit or so. So the CMB entropy is about $10^{85}$ bits.
Large black holes
However, it was found that most galaxies store a huge black hole in their center and black holes actually maximize the entropy that can be squeezed into a fixed volume, or carried by a fixed amount of bound mass. At our galactic center, the Sgr A* black hole has mass about 4 million solar masses or $10^{37}$ kg which is about $10^{45}$ Planck masses, so the radius is also about $10^{45}$ Planck lengths and the area is $10^{90}$ Planck areas, producing $10^{90}$ bits of entropy just from the single black hole.
Because there are approximately $10^{11}$ galaxies in the Universe, we get $10^{101}$ bits of entropy carried by the galactic black holes which is much higher than the CMB entropy.
Cosmic holographic bound on entropy
It may be fundamental to mention that the ultimate entropy of the Universe is bound by the area of the de Sitter horizon in Planck units. The radius of the horizon is about $10^{60}$ Planck lengths so the area is $10^{120}$ Planck areas. The largest entropy that our Universe may carry is therefore about $10^{120}$ bits. In some sense, we may say that this huge entropy is already "out there" at the cosmic horizon today - but we may attribute it to "everything that is behind the horizon" and we don't see. However, there could be lots of matter inside the horizon and its entropy could approach those $10^{120}$ bits as well. In particular, a single black hole that would grow enough to almost touch the cosmic horizon (which would shrink along the way) would carry almost $10^{120}$ bits, too. However, such a black hole will never exist, of course.
Note that Lawrence, who calculated the final bound, ended up with a figure is wrong by 40 orders of magnitude. His numbers have errors at each step. First of all, the radius of the cosmic horizon is $10^{28}$ centimeters rather than $10^{18}$ centimeters he wrote; he apparently forgot to add the speed of light or to distinguish seconds and years. This gave him the first 20 orders of magnitude of mistake. He made two more errors that produced the remaining 20 orders of magnitude.
A: The above answers correspond correctly to the holographic information storage where surface area limits the storage. Bekenstein bound is given also in other ways- `
$$    I \leq \frac{2 \pi c R m}{\hbar \ln 2} \approx 2.577\times 10^{43} m R $$
(see Bekenstein bound wikipedia), $m$ being the mass in kg and $R$ being the radius  So for a given mass of the Universe, the information limit is proportional to the radius. Alternatively for a given energy density, it goes as the 4th power of radius. At present, the energy density is $10^{-27}$ kg/cubic m and the Universe radius is $10^{26}$ m. Then the information limit is $\approx 10 \times 10^{43} \times 10^{-27} \times 10^{104} =10^{120}$ , As the wiki states this happens to be the same as the Bekenstein-Hawking entropy shown in the messages above. It seems there are several such coincidences in the epoch we are in. (See Universe horizons). (So are we at the information limit?). But note that the horizon is expanding at the speed of light, $10^8$ m/sec, and so the storage is increasing only at $10^{25}$ /sec and so (assuming total mass constant),- very very slow rate.
As a side, it seems evident how, using Hawking's own derivations, Susskind came to the, rather evident, conclusion on holographic storage of information.
A: The de Sitter vacuum has a cosmological horizon at $r~=~\sqrt{3/\Lambda}$ for $\Lambda$ the cosmological constant.  This is about $10^{-54}cm^{-2}$  This puts the cosmological horizon at about $10^{10}ly$ or about $10^{18}cm$.  Now apply the Bekenstein bound $S~=~kA/4L_p^2$ for the horizon area $A~=~4\pi r^2$ or about $10^{37}cm^2$.  The entropy is $S~=~klog(N)$ and we divide by the Boltzmann constant to get the entropy according to bits $S_{bit}~\sim~10^{80}$.  Now consider that logarithm and take the exponential of this.
