Could a computer unblur the image from an out of focus microscope? Basically I'm wondering what is the nature of an out of focus image. Is it randomized information? Could the blur be undone by some algorithm?
 A: The blurring is not randomised, it is predictable. See Can someone please explain what happens on microscopic scale when an image becomes unfocused on a screen from a projector lens? for a basic explanation.
Each point of the in-focus image is spread out into a diffraction pattern of rings called a point spread function (PSF), and these ring patterns overlap to form the out-of-focus image. The blurred image is the convolution of the object and the PSF. 
Convolution is a mathematical transformation which can in some circumstances be reversed (deconvolution) - for example when the image has been made using coherent light (from a laser) and the PSF is known. When photos are taken using ordinary incoherent light, and the PSF is unknown, the blurring cannot be reversed completely, but a significant improvement can be made, eg using the blind deconvolution algorithm. Examples of objects and resulting images can be used to approximately re-construct the PSF, or a Gaussian function can be used.  
Blurring due to motion (of the camera or object) can also be corrected. For both cases the techniques and problems are discussed in Restoration of De-Focussed and Blurred Images, and examples given of what can be achieved.
Software is available online to fix blurred images. 
A: Yes, it's called deconvolution. Here are some examples of deconvolved images from microscopes:



I found these by Googling for "example of deconvolved image from a microscope".
It's possible by shooting lasers through the lens and generating a map of ray data that can be used in the deconvolution algorithm. I have also seen this done with an in focus image and deconvolved to bring a completely different plane into focus.
A: Yes, it can be (partially) undone, because the process is not random and only part of the information is lost.
Physics
You comment that you are interested in the physics aspect of the question, so let's first clear that up: an image is focused when every point of the object corresponds to a point of the image - all the rays emanating from a given point of the object, passing, e.g., through the lens, converge to a single point (of the sensor, be it your eyes, a CCD, or a film). An image is out of focus when that doesn't happen: when these rays are spread and each point of the image receives light from different points of the object. If you know exactly the blur took place, you can try to reverse it.
That's better explained in this answer to the question Why image is blurry or focused with convex lenses?.
Algorithms
Algorithms for blur removal must work with hypotheses on how exactly the blur took place, i.e., which function better describe it, or the blurring process model. Restoration algorithms can be found in many image processing apps, but that's still an active area of research. You can read about it here and here, among many other sources. Notice, however, that restoration is only partial e artifacts seem to be always present in the restored images.
Purposeful obscuration
If pixelation is applied, though, the image is going through coarse graining, so information is irreversibly lost, and the same is true for other forms of blurring, such as averaging and addition of noise to the image: then in general an algorithm cannot recover information from the picture, because the information is not there anymore.
But, an algorithm can guess. You can train an artificial neural network for recognizing whatever you expect or want to find in the picture, and allow it to fill in the details, as explained here and here.
A: The goal with a camera lens system (whether a microscope or not) is to deliver light from one point on the object to one point on the sensor. This however cannot be perfectly achieved for several reasons.


*

*Light will diffract off the apeture, the smaller the apeture the more the diffraction.

*The system will only be perfectly in focus for an infinitely thin plane. The larger the apeture the faster the focus will drop off with distance from that plane.

*The lenses themselves will be imperfect.


All of these effects act to attenuate high (spacial) frequency components in the image. We call this blurring.
To reverse blurring we must first characterise the blurring. Characterising the blurring requires making some assumptions about what is in the image and/or the characteristics of the optical elements causing the blurring.
Once we have a mathematical function discribing the blurring process we can calculate an inverse of that function and apply it to the image.
However there are limits to how much we can mitigate the impact of blurring. Firstly because our mathematical model of the blurring is only an approximation and secondly because the inversion process inevitablly amplifies noise in the image. 
A: I've work on exactly this problem and the answer is extremely controversial! 
At the heart of the controversy is a disconnect between tomography (3D imaging) and  the surface maps (2.5D, "we all live in a hologram") approaches to image formation. The "we all live in a hologram" approach has recently seen a lot of commercial/experimental success much to the chagrin of the tomography old timers.
Different optical systems have drastically different abilities to re-focus the image.  Further, each system operates on different physical assumptions. Lets talk about a few:
Light-field systems such as the Lytro can produce selective focus for macroscopic objects, on the other hand similar affects can be achieved with digital filters. 
At low NA (>0.3), coherent (laser) illumination matches well with the linear systems approach to wave propagation in a half-space given by the Fresnel propagator. You can apply the Fresnel propagator and focus and de-focus the system, although you need some kind of measure of the complex field. Popular approaches include Hartmann-Shack style wave front sensors (similar to Lytro), traditional interferometry, and transport of intensity (TIE).  The  images in these systems look pretty terrible because junk somewhere in the beam path (perhaps a few cm away) contributes to image formation.
Now stuff starts getting wacky when coherence effects are introduced. On the other hand the image looks better under incoherent illumination. The first problem is that even for systems that are linear with the object's scattering potential (not many!), coherence introduces a spatial band limit. That is to say objects outside of the spatio-temporal coherence (you can't actually split these) radius fade away. So, now your system is only sensitive to a narrow range of object sizes, and you start getting optical sectioning. This is typically called the "coherence gating" and was famously used by OCT. In practice, you can't propagate the field beyond whats allowed by the coherence.  In most broadband systems this means you can't, digitally, move the field up-and-down by more than a few microns! (and it gets worse at high NAs)
On the other hand you can simply move the sample (or adjust the focus). When you do this a new degree of freedom is introduced, which is the origin of tomographic imaging (diffraction tomography). For people who use these kind of systems their world is made of 3D slices. They would tell you that one cannot simply refocus the light indefinitely. 
Another problem is that many systems are not actually linear with the object, for example, the infamous halo in phase contrast microscopy. In those cases you can't meaningfully digitally focus/refocus the sample because your system typically doesn't measure the field due to the sample.
On the theoretical side there is a lot of debate as to if fields are random, but the positions taken by various research groups are closely tied to their experimental setups.
A: In this article the limits of the details that can be recovered using deconvolution are derived. It's explained that noise leads to limits on how effective deconvolution can be to recover details. In the ideal case there will only be Poisson noise due to the finite number of detected photons. The smallest recovarable details scale as $N^{-\dfrac{1}{8}}$. So, getting ten times more details requires 100 million times more exposure time. Clearly, a wide aperture without a lens and attempting to focus using deconvolution, is not going to work in practice.
