When looking for the meaning of any passage of scripture the first place to look should be its context. That is the passage before and after the passage, historical context, the Testament (New or Old) in which the passage falls, etc. Let us take a look at the context of Jesus' words in Luke 23:34.
In the immediate context, the thief had spoken to Jesus and made a request. The other thief had mocked Jesus, saying, "If thou be Christ, save thyself and us" (Luke 23:39). This thief was consdidesred a criminal worthy of death, yet, he realised that he deserved what he was getting and Jesus did not. When the other thief railed on Jesus, the penetant thief responded (Luke 23:40-41):
Dost not thou fear God, seeing thou art in the same condemnation? And we indeed justly; for we receive the due reward of our deeds: but this man hath done nothing amiss.
This statement, and the subsequent request, "Lord, remember me when thou comest into thy kingdom" (Luke 23:40) indicate his repentance and faith in Jesus' Jesus answer shows that He acknowledged the thief's repentance and faith, and sets forth the controversy under discussion in this article: "Verily I say unto thee, To day shalt thou be with me in paradise" (Luke 23:42).
The word translated, paradise here means, according to Joseph Thayer:
A garden, pleasure ground, grove, park; the part of Hades which was thought by the later Jews to be the abode of the souls of pious until the resurrection: but some understand this to be a heavenly paradise.
It is clear, then, that the man is now saved.
The broader context is actually the Bible as a whole, the two Testaments in particular. Which Testament did the thief live under? He lived under the Old Testament. We will get into the importance of that fact shortly.
We know that Jesus and the thief were on the earth during the Old Testament because a look at The events of the Day of Pentecost following Jesus ascension and the fact that from that point everything points forward, while, things before that point backward. For example, in Matthew 16:18-19, the church was yet future, but, it was in the present from Pentecost forward. Jesus said, "I will build my church."
Further, in the book of Hebrews, Paul writes extensively on the fact that the New Testament has replaced the Old. That happened on Pentecost, A.D. 37 (Acts 2). He writes in Hebrews 8:10-13:
For this is the covenant that I will make with the house of Israel after those days, saith the Lord; I will put my laws into their mind, and write them in their hearts: and I will be to them a God, and they shall be to me a people: And they shall not teach every man his neighbour, and every man his brother, saying, Know the Lord: for all shall know me, from the least to the greatest. For I will be merciful to their unrighteousness, and their sins and their iniquities will I remember no more. In that he saith, A new covenant, he hath made the first old. Now that which decayeth and waxeth old is ready to vanish away.
In the broader context of the passage before us, we learn that the thief on the cross lived under the Old Testament. We will get into the importance of this fact shortly.