Caixinth, is there any evidence that aborigine “spirituality” (the preferred term) existed 60,000 or even 40,000 years ago? The dates you mention refer to indicate how long the continent has been inhabited (40,000 years is usually accepted, but some contest the 60,000 figure).
The oldest religions are probably from the middle Paleolithic period, 200,000 to 40,000 years ago or so. This is based on the assumption that the disposal of the dead has special significance for cultures that entertain certain ideas about human nature, destiny, and place. Paleolithic peoples such as the Neanderthals were known to bury their dead along with tools, trinkets, etc., as early as 50,000 years ago. This could indicate a belief in the permanence of something in a person that could survive death: the soul.
“Venus figurines,” flourished in the Upper Paleolithic (40,000 years ago) and were symbols of fertility–meaning that fertility, along with other desirable traits, may have been anthropomorphised into deities and possibly worshipped as such.
At any rate it seems fairly obvious that the oldest religion would have to be a form of paganism or pantheism, which identifies divinity and/or spirituality in nature (things such as fertility, to which our remote ancestors would have been quite closely connected). I’d like to point out that this does not mean that Wicca is the oldest religion, as some of its adherents like to claim; Wicca is actually a fairly new phenomenon.
As for early monotheism, there were more than one or two. LokiTheDog mentioned the Egyptian cult of Amenhotep IV, although he normally goes by the name Akhenaton today (Amenophis to use his Greek name). During his reign (1353–36 BC) he set up the cult of Aton, from which he took his name (it means “he who is useful to Aton”). Akhenaton’s wife, by the way, was the famous Nefertiti, a woman who adhered to his cult even when its founder started to make forced compromises with the older religious orders.
There were similar occurrences in Greek, Babylonian, Indian, and Chinese cultures.