Boltzmann brains are a theoretical prediction of Boltzmann's explanation about the thermodynamic arrow of time. Though Ludwig Boltzmann himself never discussed this concept, they came about when cosmologists applied his ideas about random fluctuations to understand the universe as a whole.
Boltzmann Brain Background
Ludwig Boltzmann was one of the founders of the field of thermodynamics in the nineteenth century. One of the key concepts was the second law of thermodynamics, which says that the entropy of a closed system always increases. Since the universe is a closed system, we would expect the entropy to decrease over time. This means that, given enough time, the most likely state of the universe is one where everything is the in thermodynamic equilibrium ... but we clearly don't exist in a universe of this type since, after all, there is order all around us in various forms, not the least of which is the fact that we exist.
With this in mind, we can apply the anthropic principle to inform our reasoning by taking into account that we do, in fact, exist. Here the logic gets a little confusing, so I'm going to borrow the words from a couple of more detailed looks at the situation. As described by cosmologist Sean Carroll in From Eternity to Here:
Boltzmann invoked the anthropic principle (although he didn't call it that) to explain why we wouldn't find ourselves in one of the very common equilibrium phases: In equilibrium, life cannot exist. Clearly, what we want to do is find the most common conditions within such a universe that are hospitable to life. Or, if we want to be more careful, perhaps we should look for conditions that are not only hospitable to life, but hospitable to the particular kind of intelligent and self-aware life that we like to think we are....
We can take this logic to its ultimate conclusion. If what we want is a single planet, we certainly don't need a hundred billion galaxies with a hundred billion stars each. And if what we want is a single person, we certainly don't need an entire planet. But if in fact what we want is a single intelligence, able to think about the world, we don't even need an entire person--we just need his or her brain.
So the reductio ad absurdum of this scenario is that the overwhelming majority of intelligences in this multiverse will be lonely, disembodied brains, who fluctuate gradually out of the surrounding chaos and then gradually dissolve back into it. Such sad creatures have been dubbed "Boltzmann brains" by Andreas Albrecht and Lorenzo Sorbo....
In a 2004 paper, Albrecht and Sorbo discussed "Boltzmann brains" in their essay:
A century ago Boltzmann considered a “cosmology” where the observed universe should be regarded as a rare ﬂuctuation out of some equilibrium state. The prediction of this point of view, quite generically, is that we live in a universe which maximizes the total entropy of the system consistent with existing observations. Other universes simply occur as much more rare ﬂuctuations. This means as much as possible of the system should be found in equilibrium as often as possible.
From this point of view, it is very surprising that we ﬁnd the universe around us in such a low entropy state. In fact, the logical conclusion of this line of reasoning is utterly solipsistic. The most likely ﬂuctuation consistent with everything you know is simply your brain (complete with “memories” of the Hubble Deep ﬁelds, WMAP data, etc) ﬂuctuating brieﬂy out of chaos and then immediately equilibrating back into chaos again. This is sometimes called the “Boltzmann’s Brain” paradox.
The point of these descriptions is not to suggest that Boltzmann brains actually exist. Sort of like the Schroedinger's cat thought experiment, the point of this sort of thought experiment is to stretch things to their most extreme conclusion, as a means of showing the potential limitations and flaws of this way of thinking. The theoretical existence of Boltzmann brains allow you to use them rhetorically as an example of something absurd to manifest out of thermodynamic fluctuations, as when Carroll says "There will be random fluctuations in the thermal radiation that lead to all sorts of unlikely events--including the spontaneous generation of galaxies, planets, and Boltzmann brains."
Now that you understand Boltzmann brains as a concept, though, you have to proceed a bit to understanding the "Boltzmann brain paradox" that is caused by applying this thinking to this absurd degree. Again, as formulated by Carroll:
Why do we find ourselves in a universe evolving gradually from a state of incredibly low entropy, rather than being isolated creatures that recently fluctuated from the surrounding chaos?
Unfortunately, there is no clear explanation to resolve this ... thus why it's still classified as a paradox. Carroll's book focuses on trying to resolve the questions it brings up about entropy in the universe and the cosmological arrow of time.
Popular Culture and Boltzmann Brains
Amusingly, Boltzmann brains have made it into popular culture in a couple of different ways. They showed up as a quick joke in a Dilbert comic and as the alien invader in a copy of The Incredible Hercules.