The adjective weird has its origins in the Old English noun wyrd, a word which was common in Old English, and which appears several times in Beowulf. Wyrd was fate or destiny, or, as the OED has, "the principle, power, or agency by which events are predetermined. The plural form referred to the Fates, the three goddesses believed to determine the course of human life. Shakespeare referred to the three witches in Macbeth as the 'Weird Sisters', with 'weird' being used in this sense.
The noun wyrd comes from the Old English verb weorþan (þ is a 'th' sound), meaning 'to come to pass', or 'to become'. Note how in German the very common verb werden means 'to become' (it's very common because it's also an auxiliary verb, used to form the future tense, the conditional and the passive).