Professor Harari notes that the clues pre-literate man leaves to his thought and motivations (mostly art) are highly ambiguous. He mentions a few of the theories that have some inspiration in that art, including matriarchy, collective marriage, and societies pretty much like more modern versions. In any case he expects that they would have been highly varied, but with some consistent elements.
We don't know, of course, and probably never will. He not exactly clear as to why he thinks this, but he thinks their religions were animistic - attributing intention, personality, and sentience to animals, plants and other features of the natural world. Such religions seem to have been common among hunter-gather peoples encountered in modern times. It was a democratic and egalitarian spirit world, with no particular personality or object in charge.
That seems to have changed with the arrival of agriculture. After agriculture, all sorts of peoples, Aztecs, Greeks, Romans, Indians, Jews and others transitioned to what he calls "big god" religions. There develops a hierarchy in the heavens, and some gods are more important than others, sometimes (like the god of Jews and Muslims), kicking all the other gods out of the pantheon. That kind of hierarchy reflects the hierarchies that develop among the agricultural peoples, with their chiefs, kings and wealthy rent extractors.