I want to let someone with more archaeological experience to discuss actual evidence of the 'earliest' 'religion', but I'll take on the question of what they would believe. Because it's impossible for us to say what they would believe - we can affirm what some early texts, maybe early indications of ritual activity, can say, but we simply cannot deduce what they believed solely from that.

I might be reading too much into your question, but I think it's an important distinction. We can take a myth like Gilgamesh, as far as I know one of the oldest written documents we have of any substance, and say what certain cultural tropes of the time were. But did anyone in that time period believe Gilgamesh actually lived at one point? Or was it simply a story to tell children--great kings kicking ass is one of the oldest stories--and held no greater religious significance? Or was he the central figure of a pantheon--much like Indra was king of the Vedic gods?

And as one might imagine, evidence of ritual activity can get even more muddled. But that's less in my field, and I don't feel qualified to answer it.

Again, maybe me being too nit-picky, but I think the question doesn't do justice to the complexity of the answer. You were most likely just asking what does early evidence say their belief system to be. Sorry if I tangented too hard, but I felt that it's necessary to keep in mind when studying other religions.

That depends on what you mean by "know about". Religious practices such as ritual burial are older than modern humans and were practiced by earlier hominid species. We don't have any clue outside archaeological observation what kind of beliefs these people had. The earliest religions that we have records of their myths and beliefs are from when people started writing (that is to say, the beliefs existed before we figured out how to record them). These are the religions of Mesopotamia and Egypt.

The Origins of Political Order by Francis Fukuyama claims that most modern religions evolved out of ancestor worship, citing Fustel de Coulanges' observation that reverence towards ancestors is almost universal in ancient religions.

Religion and kinship are closely connected in tribal societies. Ancestor worship is particularistic: there are no gods worshipped by the whole community. You have duties only to your ancestors, not those of your neighbors or your chief. Typically, the ancestor was not a terribly ancient one like Romulus, regarded as the progenitor of all Romans, but rather a progenitor three or four generations back who might be directly remembered by older members of the family.[38] According to Fustel de Coulanges, it was in no way comparable to Christian worship of saints: "The funeral obsequies could be religiously performed only be the nearest relative... They believed that the dead ancestor accepted no offerings save from his own family; he desired no worship save from his own descendents." Moreover, each individual has a strong interest in having male descendents (in an agnatic system), since it is only they who will be able to look after one's soul after one's death. As a result, there is a strong imperative to marry and have male children; celibacy in early Greece and Rome was in most circumstances illegal.

38: Maine, Early Law and Custom, pp. 53-54

We have no idea what they believed. I've commented a few times elsewhere in this thread, but it comes down first and foremost to "what is a religion". The answer seems obvious, but it's worth realizing that the contemporary usage of the word "religion" is relatively modern. How I like to illustrate this is look at the distribution of the word "god". Germanic languages say something like "gott", Romance languages say something like "deo", Slavic languages say something like, "bog", etc. because this is an indigenous concept. Religion, on the hand, has a distribution that looks a lot more like a word like "Television" than a word like "god". Why? It is not an indigenous concept, even in Europe. People had to be taught that "Hey, these things you do? That's called 'religion'." And people were usually taught this in the context of "...and they're wrong. Let me show you a better religion, in fact, the only Real Religion." See Jonathan Z Smith's chapter "Religion, Religions, Religious" for more (it's totally worth the read, I'd start every intro to religion syllabus with it if I could). Tomoko Masuzawa builds of Smith's work in her book The Invention of World Religions: Or, How European Universalism Was Preserved in the Language of Pluralism.

Lots of other scholars have come up with ideas about the origin of religion. I went through them in another comment in this thread, in response to an argument by a 19th century historian that ancestor worship was the basis for religion:

Different scholars proposed different ideas about the origins of religion: Max Müller argued for naturism as the original religion (lightning and thunder became gods name Litening and Funder), E. B. Tylor argued for animism as the original (the belief that all things had anima, souls), Durkheim and Freud argued for different versions of "totemism" as the original idea of religion (for Durkheim, totemism was essentially the collective worshiping itself; Freud's origin of religion I forget, but it's even kookier than all those above).

What do I think the earliest religion we know about is? So how we in academia should define religion is a controversial topic, but I like Bruce Lincoln's argument that we should look at four main things: community, institutions, practice, and discourse. Discourse we explicitly need to wait for writing (~5 kya) to really know about (and a lot of the earliest texts we have in almost all languages are things I'd be comfortable calling "religious"). We can see communities in the archeological records, but we can't really see what they organized around--if it was something we'd call religion, or kinship, or economy, or likely a combination of a lot of things. The first real religious institution we have a record of is Göbekli Tepe in Turkey (~12-13 kya), because most basic institutions we just wouldn't expect to show up in the archeological record (for a good intro to the site, see Elif Batuman's article in the New York called "The Sanctuary: The world’s oldest temple and the dawn of civilization")--this may also be arguably the first religious community we have unmistakeable evidence of, but there's no doubt in anyone's mind that people organized themselves around what we might call religions much earlier. Practice, however, we have evidence of much further back. The earliest religious practice is often seen as intentional burial (most animals simply leave their dead kin exposed). How old is intentional burial? Much, much older than writing, or temples, or anything else that shows up in the archeological record. Here's a thread where /u/400-rabbits explains to me some of the arguments around the issue, and says that uncontroversial dating is about ~90 kya. So what was "religion" like between 90 kya and when we start getting better evidence tens of thousands of years later? We have some hints in the form of grave goods, etc. (implying to most that the mourners believed the dead would able to take these things with them in the afterlife), but really, we don't know very much about the earliest religious practices and we're probably not going to learn a whole lot more short of a time machine. Think of most of the non-religious practices, discourses, communities, and institutions you know about. Now imagine there's no writing. How much would survive in the archeological record?

It is highly problematic to speak of a 'religion' for prehistory. The earliest 'religion' in the Durkheimian sense is Judaism. I quote from 'The elementary forms of religious life':

"religion is a unified system of beliefs and practices relative to sacred things, that is to say, things set apart and forbidden - beliefs and practices which unite into a single moral community called a Church, all those who adhere to them."

Most pre-Christian religions lack a unified system of beliefs and practices, being much more pluralist in their interpretation of the sacred. Even though watery places (springs, bogs, and rivers) are featured prominently in prehistoric ritual, this does not mean the underlying belief system (or worldview, if you will) is 'unified' in any sense.

The notion of 'religion' is highly specific, because it is modelled on Christianity, which is a very specific worldview (and quite atypical, but then again all worldviews are). If you are interested in the origin of religion, you first have to dissect the term and look at what elements are required before you consider something a 'religion'.

I can't answer the question fully but there is a rather new, and rather groundbreaking work, on this subject which I am currently reading, Michael Witzel's "The Origins of the World's Mythologies".

Again I am in the middle of reading it so I can't comment fully but he claims that by using techniques developed for historical linguistics one can reconstruct parts of early, unrecorded mythologies. He claims that most European, Asian, and Native American mythological systems are related and can be traced back to a single, secondary migration. While Australian, New Guinea, some Southeast Asian, and African myths are also related and date to the first human migration out of Africa.

Sorry I couldn't provide a more in depth answer but the material on the subject is rather new, I'm not a professional, and I haven't even finished reading the book. Assuming no one else more knowledgeable on the subject comes along though, you should definitely check out his book.

I'm not a historian (although a big fan of this subreddit!), but would Gobekli Tepe be evidence of our understanding of the earliest religion?

The main point that needs to be considered is "what is religion?" I would contend that any actions indicative of a belief in the afterlife can be considered the beginning of religion (although they are not strictly proof of religious beliefs). If that is the case, then this predates Homo sapiens sapiens. Homo neanderthalensis practiced ritualized burial, complete with grave goods such as flowers, animal parts, or tools. I don't have access to any primary sources at the moment, but this was the first sourced document I found with a simple Google search: http://bonesdontlie.wordpress.com/2011/04/25/neanderthal-burials/

The only beliefs we can reasonably infer from the anthropological evidence, which is far outside the purview of History, are that people that have died might keep living on somewhere else or as something else, and putting nice things in their graves might bring them happiness in that other existence.