Woohoo! I get to contribute! Yay!
I am getting all my information from Scientific American’s “The Hidden Mind” special edition issue (Vol. 12 No. 1), specifically out of the article entitled “The Meaning of Dreams” by Jonathan Winson.
According to Winson, REM sleep appeared in mammals around the same time as live birth. The echidna doesn’t show REM while sleeping, whereas the marsupials and placentals do. Where it gets interesting is the size of the prefontal cortex. “The echidna … has a larger prefrontal cortex compared with the rest of its brain than does any animal, even humans.”
Winson says that basically dreams are useful for processing and storing memories that are important for an animal’s survival. Instead of having to perform all its memory processing while everything happens, the animal can handle the processing when nothing else is going on. Handling everything realtime is more expensive, leading to a larger prefrontal cortex (hence the echidna’s big brain).
With the advent of dreams, brains became much more efficient, allowing for increased intellectual power with a reduced size. Hence, more adaptability with fewer resources needed, and natural selection took it from there.
So to answer the OP more succinctly, humans inherited dreaming from their forebears. Dreaming developed somewhere between egg-laying mammals and live-birth mammals, and has been a vital part of the process ever since. Whether or not a kangaroo (fer instance) can survive without dreaming, I don’t know.
If you find this interesting, I’d recommend the article I mentioned above. The author does a much better job than I in describing what’s going on, and the rest of the issue is very interesting as well.