This is an answer from the point of view of the Catholic Church (but which might also represent other Christian denominations).
The Catechism of the Catholic Church (a document which summarises the beliefs of the Catholic Church, emerging from centuries of theological scrutiny [notice theology tag in the question]), states the following:
I. The Desire for God
27 The desire for God is written in the human heart, because man is created by God and for God; and God never ceases to draw man to himself. Only in God will he find the truth and happiness he never stops searching for:
The dignity of man rests above all on the fact that he is called to communion with God. This invitation to converse with God is addressed to man as soon as he comes into being. For if man exists it is because God has created him through love, and through love continues to hold him in existence. He cannot live fully according to truth unless he freely acknowledges that love and entrusts himself to his creator.
28 In many ways, throughout history down to the present day, men have given expression to their quest for God in their religious beliefs and behaviour: in their prayers, sacrifices, rituals, meditations, and so forth. These forms of religious expression, despite the ambiguities they often bring with them, are so universal that one may well call man a religious being:
From one ancestor (God) made all nations to inhabit the whole earth, and he allotted the times of their existence and the boundaries of the places where they would live, so that they would search for God and perhaps grope for him and find him - though indeed he is not far from each one of us. For "in him we live and move and have our being."
Importantly, this desire for God is there from the beginning of human kind. As humans have been distributed all over the world, so different religions and belief spread throughout the world. The key is that those different gods represent idiosyncratic features of the satisfaction of a common desire, i.e. to seek [the true] God.
Moreover, according to Judeo-Christian religions (Judaism, Christianity, and some might even say Islam), God did not remain invisible all the time. He decided to revealed Himself to some individuals and groups. The Catechism states:
Through an utterly free decision, God has revealed himself and given himself to man.
This revelation was progressive in the sense that He revealed only parts of Himself at a time. For instance, God chose Abraham in order to build a "chosen people", which later on gave rise to Judaism. According to Christianity, God's self-revelation was fulfilled (i.e. finished) in Jesus Christ, giving rise to Christianity.
The above is an example of why there are different religions and "different gods", according to one Christian tradition.