Imagine the Pleistocene.
Imagine small groups of intelligent, talking, tool using primates living in small bands.
The social structure of such groups would have been complex and likely involved pretty intense interactions. In modern pastoralist and hunter-gatherer societies life is not easy, and there no reason to think that it would have been in the past. There was likely starvation, disease, and, of course competition with other bands of hominids.
Individuals in these groups likely gained by conforming to group ideology (hairstyles, dancing, food processing, and, of course, interpretation of reality [religion]) both by gaining individual support and reinforcing group allegiances. It would not suprise me at all if this dynamic has been inplace long enough for natural selection to have favored hominids who had some kind of desire for learning a group's interpretation of reality.
The desire to adhere to group philosophy is not restricted to the so-called monotheistic religions. Lots of different religions tap into this same innate human tendency.
It is just survival in groups, thats all.