Let's move away from armchair speculation into what we can make of the facts so far. I think our best bet is that religion is a confluence of certain social and cognitive factors that when they happen to align in a certain way, we call it "religion." (Getting into the problem of defining religion is another problem as well.)

What the precise content of the earliest religion was, there's no real way to say. Based on historical and ethnographic records, there is no real reason to suppose it looked like what we call religion today. The earliest symbolic behavior has recently been found in an engraved shell associated with an H. erectus ~500,000 years ago. What this means, we really have no idea. The first uncontroversial find that has been linked to religion are the ceremonial burials at Qafzeh and Skhul caves in present-day Israel. This may indicate some sort of belief in ancestor worship, an afterlife, or spiritual guidance by dead ancestors. That's about the extent of what can be said about any beliefs related to these burials.

A possible reconstruction of what early religions might have looked like based on ethnography and history can only give us some generalities. Two popular answers are the classic functionalist theory of group cohesion, or the intellectualist answer that early religion was a bad way of explaining physical phenomena, basically a pseudo-science. The former fails because morality and religious belief are not universally connected. It is easily more conceivable that morality and concepts of the supernatural evolved along separate lines and became intertwined at specific historical periods. The latter is also untenable because it assumes that people seek explanations for everything, which is not always the case cross-culturally.

To take a very extreme example, the Piraha of the Amazon have only the most minimalist concept of anything that could be called a religion. They have a three-tiered cosmology and spirits. The spirits, however, do not interact with them all that much and they don't serve as explanations for physical phenomena or figures of moral guidance. If anything, they are hyper-empiricists -- anything that they can't experience directly might as well not exist. This is why Dan Everett, when he went on a mission, failed to convert them. This actually stretches back to the earliest missionaries, many of whom had trouble converting indigenous peoples because their concepts of religion were so incredibly different.

We also run into another problem with ontology in the sense that not all societies have a concept of a division between natural and supernatural. One example is the Nayaka in India. There are unseen entities in their belief system, but they are conceived of as natural entities. The word "superperson" has increasingly been used to refer to these entities.

What might we be able to say? Middle Paleolithic religions would very likely have looked very different from any of today's world religions. Some characteristics may have included the following: Some may have had the concept of spirits, some may have had superpersons. Ceremonial burial was a common ritual. Morality was not particularly connected to spiritual ideas. There were few, if any, religious specialists. Beliefs were probably not a specified set of doctrines. A tiered cosmology may have existed. By the Upper Paleolithic, religious specialists developed in the form of shamans. In certain regions of Europe, going by cave art, rituals may have included going deep into caves. This could help in achieving altered states of consciousness through sensory deprivation. It is difficult to go to anything beyond some of these generalizations.

Sources: Asad, Talal. The Construction of Religion as an Anthropological Category

Atran, Scott. In Gods We Trust

Bird-David, Nurit. Animism Revisited

Bloch, Maurice. Why Religion is Nothing Special But Central. Boyer, Pascal. Religion Explained

Everett, Daniel. Don't Sleep; There Are Snakes.

Fowles, Severin. An Archaeology of Doings.

Jordans et al. Homo erectus at Trinil on Java used shells for tool production and engraving

Lewis-Williams, J. David. The Mind in the Cave

Mayer, Vandermeersch, and Bar-Yosef. Shells and ochre in Middle Paleolithic Qafzeh Cave, Israel: indications for modern behavior

Owens and Hayden. Pre-Historic Rites of Passage: A Comparative Study of Trans-Egalitarian Hunter-Gatherers

Stark, Rodney. Gods, Rituals, and the Moral Order