The sources known to us today which give the earliest legends known from Wales are the opening four sections of the Mabinogion, the work now often regarded as the canonical compilation of old Welsh myths and legends. These four "branches" tell of heroes who were once worshiped as Gods, and in a straightforward voice reminiscent of the Icelandic Sagas they present the ambitions, triumphs, and betrayals of these characters. But the history of the Mabinogion - and even of the idea that there is such a book - reveals far more than just what tales were told in high medieval Wales.
The first archaeological evidence for peoples we can recognize as being Celtic (meaning they spoke languages more closely related to Gaulish than to Latin) comes from southern France ca. 600 BCE. By about three centuries later, Celtic cultures reached their maximum extent, spanning vast swaths of Europe; as a result of Roman conquests, Celtic culture outside the British Isles mostly died out in antiquity. Roman sources preserve names of Gaulish gods and some information about Gaulish religious practices, but not any mythology (and a lot of references don't even give names, due to the widespread use of the interpretatio romana); in the British Isles, mythological stories weren't written down until after the people had converted to Christianity.
The Old Irish Lebor Gabala Erenn ("Book of Invasions of Ireland") and other "mythological cycle" texts from that period preserve a great quantity of pre-Christian Irish mythology, shoehorned into a framework consistent with Christian belief. For example, it presents the old gods of Ireland as being heroes of the tribe which had settled in Ireland before the current inhabitants, and who have been mistakenly worshiped as gods.
Welsh material, however, is substantially more altered. The earliest stories contain characters whose names correspond directly to those of Irish and Gaulish deities - for instance, the Welsh Lleu (The modern Welsh form is given here, and throughout this post), Old Irish Lug, and Gaulish Lugus all stem from the same proto-Celtic root. Lug was sometimes known as Lugh Ildanach in Middle Irish, with the epithet translating as "skilled in many things" (I have not found the Old Irish form of this epithet but believe it to have been substantially similar), while the Welsh character is given as Lleu Llaw Gyffes, "Lleu of the Skillful Hand." There are also parallels thematically between some of the stories; both Lleu Llaw Gyffes and Lug are attacked after their wives are unfaithful. Lug is killed by the sons of his wife's lover, whom he has killed, while Gronw Pebr, the lover in the Welsh story makes the first move and attempts to kill Lleu Llaw Gyffes, who later kills him as revenge. But the similarities are weathered by the passage of time, and by the telling of legends in a Christian context. Lleu Llaw Gyffes, his wife Blodeuwedd, and her lover Gronw Pebr are not gods, but mortals (although Blodeuwedd is not precisely human); they and the rest of the characters in the Mabinogion are legendary heroes who have some amount of supernatural power attributed to them but are not spoken of as remotely divine. Lleu Llaw Gyffes is not associated with storms, for example, though the Gaulish Lugus was almost certainly a storm god and Lug probably was as well (though he is not recorded as such in the post-conversion writings we have available). In fact, there are references to the idea of Gronw Pebr himself practicing a religion, which would make no sense if he were a god, and many of the central characters are mentioned as being lords or kings of various places and even appear elsewhere on pseudohistorical king lists.
The go-to source for these stories is the Mabinogion, a book of Welsh legends that did not exist until the nineteenth century.
The name Mabinogion is an error, though a medieval one. There are a set of four texts which appear in two major manuscript sources which identify themselves in the text as the four branches of the Mabinogi, a word of uncertain derivation but which is already plural; in one text of one of the four, the scribe has appended the common Welsh plural suffix -on to this word.
These four branches each tell a series of stories which are interlinked and do not neatly divide from one another within a branch. The story of Lleu Llaw Gyffes, for instance, appears in the fourth; in discussing the adventures of Gwydion, King of Gwynedd, Lleu's birth is mentioned, followed by a discussion of the creation of Blodeuwedd, followed by her affair with Gronw Pebr and their attempt to kill Lleu, followed by Lleu's revenge (obtained with the help of Gwydion), followed by a mention of Lleu's inheritance of his uncle's kingdom. Even Gwydion's story doesn't begin neatly, flowing seamlessly out of the narrative about his uncle, Math ap Mathonwy.
The Mabinogion as we know it today is a creation of modern antiquarians. It is a compilation which begins with the four branches of the Mabinogi, and then includes additional unrelated stories also drawn from medieval Welsh manuscript sources. These stories are not believed to much predate their manuscripts, with the probable exception of the character of Lludd Llaw Eraint ("Lludd of the Silver Hand"). Lludd's forename appears with an initial nasal in the earliest texts; the later name likely derives from the phonetic similarity to Lleu and from the shared initial with the epithet. No reason is given for the full name in any Welsh source, though it directly corresponds with the Old Irish Nuada Airgetlam "Nuada of the Silver Hand." (Nuada is the king of the gods until forced to abdicate after losing his hand in battle; the smith god Goibniu then fashions him a fully-functional replacement out of silver. Lludd is also a great king, but has no corresponding adventure.)
Today, the standard version of the early Welsh legends is the Mabinogion as published by Lady Charlotte Guest in the early 19th century. Guest's Mabinogion appeared with parallel text, translating the Old Welsh of the original stories into contemporary forms of both Welsh and English. Her set of seven stories to include after the original four branches of the Mabinogi has been followed by other authors as well.
Importantly, several of these later stories contain a character familiar from other stories: a king who plays a decidedly secondary role, but bears the familiar name of Arthur. The texts Guest includes, in particular Culhwch and Olwen, seem to be the earliest forms of a nascent Arthurian legend available to us. It is likely the presence of Arthur that prompted Guest to include these tales, as interest in the Matter of Britain was on the rise in England at the time. In the process, however, Guest brings the entirety of her Mabinogion into a context moderately foreign to the initial composition of its oldest texts, implicitly placing the lives of characters derived from the pre-Christian gods of Wales into the age of chivalry. Of course, that age of chivalry is itself a sort of mythic dreamtime, as any historical antecedent for Arthur must have lived centuries before the institution of knighthood, so perhaps it is a fit home for the gods-turned-heroes who populate the four branches of the Mabinogi.