My cats, and I assume others, show signs of movement in their sleep similar to what people show when they're dreaming. There seems to be some schools of thought that suggest that cats do dream, but is this really the case or are we just projecting our experiences on to them?
Cats do dream when they sleep. The phenomena you are observing is related to sleep patterns that are also observable in human beings.
There were (perhaps unfortunate studies) performed on cats to demonstrate the part of the brain responsible for for allowing movement when dreaming. A phenomena called REM sleep without atonia (RWA),
Michel Jouvet did some, now, famous experiments on sleeping cats, where he created lesions in the peri-locus coeruleus and demonstrated the variation between paralysed REM sleep and RWA. From this they were able to deduce the part of the brain responsible for preventing movement during sleep.
REM sleep without atonia (RWA) and "oneiric" behavior that could only be explained by "acting out dreams" (or "dreaming out acts"), (1)
- (1) Rem sleep without atonia--from cats to humans.
Mahowald MW, Schenck CH.
As Skippy says, cats definitely dream.
For a slightly less disturbing reference, this article summarizes the current state of the research and includes a brief biological explanation (the short version is that the hippocampus operates the same way in almost all vertebrates including mammals - meaning that if it's got an internal skeleton it probably dreams): http://www.petsitusa.com/blog/?p=3363
(As a side note - and a personal one - this means that pets can also suffer sleep disorders similar to the ones we humans get to deal with... I'm narcoleptic, and a good deal of the knowledge about how narcolepsy works comes from observations of narcoleptic dogs).