St Matthew tells us that the Magi returned to their country by another way, and so they leave the pages of the Gospel, but tradition, legend and piety has not stopped there.
They acquired names and kingdoms - Caspar, King of Tarsus -the land of Myrrh, Melchior, King of Arabia-the land of Gold, and Balthasar, King of Saba (pron SAY-ba) or Sheba- where Frankincense flows from trees. [Ancient Ind, Persia,Kasdim-Chaldea] - and were provided with a history.
"When the Children of Israel were gone out of Egypt and had won and made subject to them Jerusalem there was in the Kingdom of Ind a tall hill called the Hill of Vaws or the Hill of Victory. Twelve clerks of astronomy kept watch for the Star that was prophesied by Balaam to be the birth of Christ." The Star ascended above the hill and was seen by the three wise men. The Three Kings presented their gifts of gold, frankincense, and myrrh to the Christ child. Gold symbolized kingship, frankincense showed godliness, and myrrh death. In return, He offered charity and spiritual riches for gold, faith for incense, and truth and meekness for myrrh.
The Kings returned home by a different route and St. Thomas found them in India and baptized them. They became martyrs and were buried outside the walls of Jerusalem. They were moved to Constantinople by Emperor Constantine’s mother St Helen to the Church of Hagia Sophia, and then to Milan. Finally in 1164 Archbishop Rainald of Dassel translated what were believed to be their relics to his cathedral in Cologne, where they continue to be venerated.
The Archbishop died in 1167 and the great reliquary which holds the bones was constructed between 1180-81 and about 1225, and is arguably the greatest surviving of all medieval relic chasses.
Around the relics there developed an extensive devotional and hagiographic literature. The text of an Early English translation of The Three Kings of Cologne by John of Hildesheim in its 1886 edition can be read here
I have heard the charming story that the church bells along the Rhine spontaneously rang as the relics passed by on their journey to their new home - it may be poetic licence, but it is a rather splendid notion.
There is an illustrated article about the Three Kings Shrine here and another with more detailed illustrations here.
As to the relics themselves and their provenence I have seen a documentary about them which pointed out that some of the wrappings were made from early and expensive Byzantine silk - these were well attested relics long before they came to Cologne.
The Shrine of the Three Kings in Cologne Cathedral