The Dreamtime is a mysterious dimension (of a sort), where one's surroundings are molded by one's wishes and desires. Apparently, it can only be entered with the mind, not physically. According to the Shaman, there may also be some connection between the Dreamtime and Avalon, but in what way remains unclear. 
Dingo's shaman mentor sent Goliath and Dingo into it in order to communicate with the Matrix and persuade it to stop reformatting the world, since it was the only place where they could communicate with it. ("Walkabout")
Real World Background
In Australian Aboriginal belief, the Dreamtime is not actually another dimension, but rather the time when the world was newly created, and the events took place that shaped humans, animals, plants, and the Earth itself as we know them today, a sort of "Mythic Age."
Greg Weisman has insisted that any future mention of the Dreamtime in the series would require further research of the original Australian Aboriginal concept, and that any Canon-in-training regarding the Dreamtime remain particularly tentative until it's planned to make an appearance in a future story. 
- Dreamtime at Wikipedia, the Free Encyclopedia