Gospel of Nicodemus
The earliest known record of the thieves' names occurs in the anonymous work which eventually (several centuries later) became known as the Gospel of Nicodemus. The work is basically orthodox in nature and was likely composed in the early-mid fourth century. The first part of the work purports to be a translation of the official trial record of Jesus' crucifixion, written by Pilate. Although few, if any, scholars consider it possible that the so-called Acts of Pilate reflects an actual letter of Pilate, most do believe it was a significantly earlier work incorporated into the Gospel of Nicodemus.
The Acts of Pilate was likely written in the late second century. Earlier, around 155, Justin Martyr wrote:
And that these things did happen, you can ascertain from the Acts of Pontius Pilate. (The First Apology, Ch. 35)
thus suggesting his reader consult the official trial log of Pilate. Whether such a log actually existed or Justin Martyr just assumed it did cannot be known. Either way, scholars generally think the Acts of Pilate was written to answer critics who were calling for the document to be produced.
There are two thief passages of Gospel of Nicodemus, both found in the Acts section. The textual tradition of Gospel of Nicodemus is fairly corrupt, resulting in two fairly different readings.
The first passage reads, in the better attested (Greek) version of Nicodemus:
Then Pilate ordered the curtain of the tribunal where he was sitting to be drawn, and says to Jesus: Your nation has charged you with being a king. On this account I sentence you, first to be scourged, according to the enactment of venerable kings, and then to be fastened on the cross in the garden where you were seized. And let Dysmas and Gestas, the two malefactors, be crucified with you. (Ch. 9)
The other version is not significantly different. The second passage reads:
And one of the malefactors hanging up spoke to Him, saying: If you are the Christ, save yourself and us. And Dysmas answering, reproved him, saying: Do you not fear God, because you are in the same condemnation? And we indeed justly, for we receive the fit punishment of our deeds; but this man has done no evil. (Ch. 10)
the other (Latin) version reads more straight-forward, not incorporating the Gospel-like language:
And in like manner did they to the two thieves who were crucified with him, Dimas on his right hand and Gestas on his left.
The Arabic Infancy Gospel, written around the sixth century, and The Narrative of Joseph of Arimathea, date unknown but probably later than that, greatly expand the story.
In the Infancy Gospel, "Titus and Dumachus" meet the Holy Family on their way to Egypt and Titus, the good thief, convinces Dumachus not to physically harm the family. The young Jesus then prophesizes:
Thirty years hence, O my mother, the Jews will crucify me at Jerusalem, and these two robbers will be raised upon the cross along with me, Titus on my right hand and Dumachus on my left; and after that day Titus shall go before me into Paradise.
The The Narrative of Joseph of Arimathea is probably dependent on Gospel of Nicodemus. It contains some details about Demas' (so spelled in this account) life:
He was called Demas, and was by birth a Galilæan, and kept an inn. He made attacks upon the rich, but was good to the poor— a thief like Tobit, for he buried the bodies of the poor. And he set his hand to robbing the multitude of the Jews, and stole the law itself in Jerusalem, and stripped naked the daughter of Caiaphas, who was priestess of the sanctuary, and took away from its place the mysterious deposit itself placed there by Solomon.
and has a very long, detailed of Demas' confession of faith.
In Codex Rehdigeranus (8th century), the names Joathas and Maggatras are inserted into the Gospel account. In Codex Colbertinus (12 century), the names Zoatham and Camma are inserted into Mark and the names Zoatham and Chammatha are inserted into Matthew. The 17th century Codez Bezae has Gemas and Demas.1
It seems nearly every account gives different names to the thieves. This highly suggests that the names were made up. They probably were not known even in the very early church, as there really would have been little reason for anyone associated with Jesus to have known the other criminal's. They were just random criminals - not associated with Jesus' trial or anything like that.
Additionally, there is a strong tendency in apocryphal texts to give names to nameless figures and otherwise fill in "missing" details of the canonical Gospels. The same thing almost certainly happened here. The Greek name Dysmas, perhaps derives from the word dysme which means "sinking" or "setting", thus suggesting "dying".2 This suggests that the name may have been invented to fit the context.
So the real answer is, "we don't know." If we insist on names then Dismas (or Dysmas) for the repentant thief and Gestas for the unrepentant one is the best we can do. It is the earliest account and there is small chance the Acts of Pilate has a historical core.
1 The Gospel according to Luke by James R. Edwards
2 EWTN Catholic Q & A by William Carroll