Mythology is the attempt to create a single coherent canonic narrative out of the religion1 and myths of a certain culture.
Mythology can only be created by societies that have reached a certain level of development and that are beginning to establish a sense of national or religious distinction from other societies, that is beyond the question of political boundaries2.
The earliest examples we have of an attempt to canonise myths and thus create a coherent narrative is in pre-archaeic and archaeic Greece3, especially in the writings of Homer and Hesiod4.
The two works attributed to Homer (the Iliad and the Odyssey), are perhaps the most distinguished and famous examples of a popular epos5, and thus show how mythology can be created spontanuously, and indeed in the Homeric work there is an attempt to incorporate local myths into the Pan-Hellenic consciouceness, by organizing and emphesizing the important Deities that are common to all (or most) Greek settelments (cf. Olympic Deities), on the expense of local Deities (although they also are mentioned occasionally, their role is very limited as they can appear only in parts created in their locale). However it should be noted, that although there is a serious attempt in the Homeric works to create a common mythology for all the Greeks in the first time, the Iliad and Odyssey completely ignore the Chthonic layer of the Greek religion. Hecate, for instance, is not mentioned in these poems even once, despite the fact that she had a major cult with many worshippers in Ionia, the region in which a large part of these works was composed.
Hesiod's works, in contrast, although certainly in the artistic epos5 category, represent a much earlier stage of Greek religion, and in them the Chthonic traditions are shown in much more detail and emphasis than in Homer's.
This contrast between the two layers of Greek religion (the Olympic and Chthonic ones) was perhaps the greatest gap on which Greek Mythology had to bridge, and it is evident that it didn't always manage to do so. Even in later eras poets tended to ignore one of these layers when they wrote epics, and as Homer was considered more important than Hesiod, the Chthonic Deities and traditions rarely appear in the writings of later artistic epos writers (from Diodorus to Ovid), despite the fact that they continued to be a prominent (sometimes more prominent than the Olympic ones) part of actual religion.
We have a rather detailed documentation as to creation of the Jewish Mythology, that, unlike the Greek one, was edited in a single scripture (the bible), which became holy, not only in contents, but in actual form. We know of many discussion regarding what should go into the canon and what should be left outside (Esther and the Song of Songs almost didn't make it). Many of the books that didn't make it, managed still to recieve a sacred status as the Apocrypha6.
1 Modern research defines religion (and thus distinguishes it from myth and mythology) as the practices of worship and faith existing in a certain culture. Myth (and consequently Mythology) set the background and excuses for religion. This way the Communion of the Catholic Church is religious, as are the Mass, Confessions and Holidays, whereas the Biblical text is Mythological. Religious practices quite often predate their mythic (and certainly mythological) reasoning.
2 this way the Greeks could create a mythology, even though they were seperated into hundreds of small political units, as could the Jews despite having no intependent political unit of their own for the majority of period of their shaping their mythology (aka the bible).
3 the tale of Gilgamesh far precedes the creation of the Greek epic cycles, but since we do not have enough evidence as to the local myths of the period preceding the creation of Gilgamesh, and of the way they were incorporated into his tale, I (as many other researchers do) will not refer to it as an example for the creation of a mythology.
4 There were many other important epic poets in the period of those two poets, however none of their writings survived, and so we cannot really know what they wrote (cf. The Trojan Cycle and The Theban Cycle).
5 popular epos is the creation of an epic poem not by one poet who writes an entire poem by himself and then publishes them (what is known as an artistic epos), but by many travelling singers (minstrels of sorts), each adding to the poems the traditional myths of his own homeland, or the traditions of the place where he was performing, the form of popular epos is characteristic to prehistoric societies or ones with extremely high illiteracy, as the use of writing prevents the texts from evolving and make this genre obsulete.
6 Only in Christianity. Judaism does not consider the Apocrypha sacred, though some of the books (particularly Maccabaei) are considered to have great historical importance.