I have a theory on what dreams are, if anyones interested.
First a little theory on how brains work, I wont ramble about this too much. I think brains (when I say brains I'm talking pretty much just about the cortex, the part of the brain that does the stuff we think of when we think of brains), are a hierarchy of nodes that recognize common patterns, tell their hierarchically superior node what sequence of patterns they are seeing, and send predictions about the next pattern they will see to the nodes below them. So if you were feeding numbers into a node, it would first of all recognize each of the numbers because it had seen them before, and stored their spatial pattern. Then it would recognize the most common temporal patterns of these numbers, and assign an arbitrary label to them. So if it saw 1, 2, 3, 4 a lot, then it would remember that, and when it was seeing part of that pattern, it would send the arbitrary label up to its mother node, even if it didn't have the complete pattern. Also, if it saw 1, 2, 3, then it would see that the 1234 pattern was likely coming in, and send down a prediction of the number 4 to its children nodes. The children nodes could use that to resolve any confusion. If the predictions get all the way down the hierarchy, with agreement all the way, then you have understanding.
As a more relative and real example, people sometimes lose part of their visual field for whatever reason. A section of neurons will stop sending information into the brain. For a good chunk of people that this happens to, they will eventually start seeing strange and almost random things in that blind spot, with a superphotorealism quality. They look more clear and real then the stuff they are actually seeing. What I think is happening is that without any conflicting input coming in, then neural signals higher up in the hierarchy will activate adjacent unused parts of the hierarchy randomly, and start sending down garbage. Without the conflicting input, then whatever random thing happened to be sent down will be agreed upon by the entire hierarchy, to the primary visual cortex and then will appear real to the person.
Using that phenomenon, and the fact that when in the sleep state where you dream neurotransmitters that connect your sensory and motor to your brain are suppressed, then I think dreams are simply random garbage coming down the hierarchy. With no conflicting input then it feels real because it is activating your brain in the same way as real input does. I also think that sometimes a dream feels very powerful and emotional, even though it may have just been random stuff is because the garbage activation is propagating down all the way to the emotional centers of the brain, and creating a highly emotional and meaningful experience.
B.O.B. asked if bacteria or cells sleep, and the answer is no. Sleep is a function of having a certain type of brain, and really is mostly in vertebrates. Also Mathias, we only dream during REM sleep.