How many bits are needed to simulate the universe? This is not the same as: How many bytes can the observable universe store? 
The Bekenstein bound tells us how many bits of data can be stored in a space. Using this value, we can determine the number of unique states this space can be in.  
Imagine now, we are to simulate this space by enumerating each state along with which states it can transition to with a probability for each transition.
How much information is needed to encode the number of legal transitions and the probabilities? Does this question even make sense? If so, is there any indication that any of these probabilities are or are not Computable numbers?
Edit
Here's a thought experiment.


*

*Select your piece of space and start recording all the different states you see. 

*If the Bekenstein bound tells us we can store n bits in our space, wait until you see 2^n different states. Now we've seen all the states our space can be in (otherwise we can violate the Bekenstein bound).   

*For any state, record any other state that the space can legally transition to without violating any physical laws.


To simulate this portion of space, take it's state and transition it to a legal state. Repeat.
We have only used a finite number of bits and we have modeled a section of space.
 A: I will add to  @Lagerbaer's estimate that  the prevailing physics theories do not describe the universe as a LEGO constructable entity. 
When you see a man figure sculpted by lego bricks, you can ask " how many lego pieces went into simulating that man, because there is a finite size for a man and a finite size for the lego brick.
Even though the Universe has a finite size, there are no finite lego bricks that can simulate it. You need some calculus similar to what mathematicians use when counting and manipulating infinities.
A: Bits, or qubits? Classical or quantum computer? Exact simulation accuracy, or good enough accuracy?
If perfect accuracy, the computer can't be part of the universe because no finite entity can simulate itself with perfect accuracy. The measurements also have to be performed at the meta level. 
A: The number of bits in any form is so close to infinite, that it doesn't make much sense to estimate it. Continuing in Lagerbaer's method, let's suppose we can find a ten-parameter fit to electronic wavefunctions for each electron, not using a grid, but using some parameters that describe the center position and spread, and oscillations.
The phenomenon of entanglement means that you need a hundred-parameter fit for 2 electrons, and for 10^80 electrons, you need
$$ 10^{10^{80}}$$
numbers, or if you want to be pedantic in terms of bits, assuming double precision is good enough:
$$ 10^{10^{80}+2}$$
This is an order of magnitude which is totally false, since I left out the huger number of photons. If you want to describe the wavefunction of photons (and protons and neutrons), then you need a lot more numbers in the double exponent.
This estimate is mind-bogglingly absurd--- the majority of this wavefunction is describing highly entangled superpositions of particle positions that are nothing like what we observe classically. A classical description requires
$$ 10^{80} $$
bits, give or take, since it scales linearly with the number of particles. This mismatch in scaling between quantum mechanics and classical approximation to the universe is what makes a lot of people uneasy with taking quantum mechanics seriously as the final theory. What possible use is there in requiring such a vast number of bits for simulation? Wouldn't it be nicer to have a theory which has the right number of bits? The vast computational space of quantum mechanics is also what makes people interpret it as a many-worlds theory, it is spreading into a space of possibilities that is so staggeringly huge, and our status in the theory only lets us see a tiny little subpart of this enormous space.
One can take the view that quantum mechanics is complete, and since it is so much vaster than classical mechanics, even a modest size quantum computer, on the order of 10,000 qubits, can do factoring calculations that exceed the capacity of a classical computer of $10^{80}$ bits. If we build such a computer, it will be hopeless to reduce the description to a classical one.
But we haven't done so yet, so a serious question remains: does there exist a theory in which you can reduce quantum mechanics to a managable size? Can you reproduce the dinky quantum mechanics which we see, which is essentially just classical mechanics with occasional quantum effects, with a theory which is fundamentally classical?
The one thing we know for sure is that we can't do this locally. If you use a local classical model, you will fail to reproduce Bell's inequality violations. But gravity is known to be nonlocal, and one can (barely) imagine a nonlocal classical computer conspiring to produce something that looks like quantum mechanics for some sort of embedded observers. Nobody has such a theory, but if it makes a computation the size of the classical universe, it will predict that quantum computation will fail when factoring large enough doable numbers.
A: There's a huge difference between the number of bits you can store in a given space and the number of bits you need to describe that space.
Take a single atom of iron with its 26 electrons. For a complete description, you need the many-particle wavefunction $\psi(\vec{x}_1, \vec{x}_2, \vec{x}_3, \dots, \vec{x}_{26})$ (ignoring spin for the moment). Imagine you want to sample it in a given region of space with a very crude grid of 10 points for each direction, so you have $1000$ points in total. 
This means you need $1000^{26} = 10^{3\cdot 26} = 10^{78}$ numbers to store it. For decent precision, you want to use at least $16$ bits, so you end up with approximately $10^{79}$ to $10^{80}$ bits. This is more than (or of the same order as) there are atoms in the entire universe. 
Now taking it up from here, for a super-exact simulation of the universe you need the complete wavefunction of the entire universe, so replace the $26$ from the example above with something much higher, and of course you want it to be more precise, so replace the 1000 with something much higher, and then note that due to quantum field theory, the number of particles isn't even fixed, so a simple wavefunction isn't even enough... In a black body, for example, you can have an infinite number of photons. Although the probability for this decays exponentially, you'd still have to include it in an exact simulation...
A: Anyway you look at it, you need an infinite number of bits. This is because if you have only a finite number, then you can't describe the description, as Konard stated. That is unless the description happens from outside of the universe. In that case the question is simply weather the universe has an infinite amount of information in it or not.
I don't know any proofs that the universe is composed of infinite information, and some views relate energy and information (a proof that it is possible to convert information to energy can be found in Maxwell's demon thought experiment which was allegedly proved here http://www.livescience.com/8944-maxwell-demon-converts-information-energy.html), so if you believe there is a finite amount of energy, then maybe this means that there is also a finite amount of information, so only a finite amount of information can be used to describe it.
However, as far as I know, most physical theories today require continuity and make use of it, so this number of required bits is obviously infinite. So if you believe that, you may be able to describe the universe from within (like Borges' short story "The Aleph" http://www.phinnweb.org/links/literature/borges/aleph.html). It seems to me that in this case the interesting question is whether we have a continuous universe or not. Whether space is enumerable or not. I asked this question yesterday here Can we have non continuous models of reality? Why don't we have them?.
A: Multiply the area of the cosmological horizon by 4 - you'll get the needed information quantity in nats. Convert into bits by dividing by $\ln 2$. You'll get the needed value.
