It may be wortwhile to note that, during the time of Jesus, the Jews had a concept of two places in the afterlife: Geihinnam (variant spellings exist), and Gan Eden, also known as "the Garden of Eden." The Talmud and midrashim are replete with such mentions.
What does this have to do with "paradise"? Well, we derive the English word "paradise" in the KJV and other English translations from the Greek word παράδεισος, the same word translated into English as "paradise" in Luke 23:43. (Yes, there is an earlier Old Iranian root, but that's not the point.) This same Greek word is used in the Septuagint (LXX) to translate the Hebrew phrase גַן־עֵדֶן (gan eden) in the Tanakh. What this tells us is that "paradise" is equivalent to "the Garden of Eden."
Hence, Jesus was saying that the thief on the cross would be with Jesus in the Garden of Eden that day. Did this happen?
Some insist that it did not because Jesus' body was 3 days and 3 nights in the sepulcher ("the heart of the earth"). This is true, but Jesus wasn't just a body. His spirit went to paradise that very day, along with the spirit of the thief on the cross. If you carefully read Paul's writing in 2 Corinthians 5 (e.g., "in this we groan" --- what does "this" refer to, and who does "we" refer to?), it should become evident that we continue to exist although our bodies remain in the grave.