Remember that the original Greek didn't use punctuation, and whatever you see in English versions has been added by the translators, often based on their previous understanding of tradition.
In this case, the appropriate place for a comma in that verse could have been inserted after, rather than before the word "today".
That would give it a completely different meaning. Compare:
- Verily I say unto thee, today shalt thou be with me in paradise.
- Verily I say unto thee today, shalt thou be with me in paradise.
How can we know which one is the correct interpretation?
One way is to observe the use of sentence structure in Greek. The thief's statement was "remember me when thou ...". A balanced response to that would match the "when" with the "today". That is, Jesus tells him that there is no need to wait until the Kingdom, that He can tell him right away.
An even stronger indication that this is what was actually meant is given by matching more explicit facts given elsewhere in the Bible. In John 20:17, Jesus says "I am not yet ascended to my Father" and this is after the Resurrection. He had just spent three days and three nights in the grave, so the thief couldn't possibly have been in paradise with Jesus on the "today" mentioned during the crucifixion.
The comma goes before "today", Jesus lied, or the Bible contradicts itself. Which do you think it is?
All we know for sure then is that Jesus assured the thief that he would be with Jesus in "Paradise" when Jesus has his Kingdom.
Some denominations teach that the Kingdom of God is here on Earth now, so I can't speak for them. But others believe that the Kingdom will be here on Earth for a thousand years following Christ's return. At the end of that Millennium, there will be a second resurrection of those that died without ever being offered salvation (Rev 20:5), the vast majority of mankind. It is then that they will live in God's Kingdom, as physically resurrected people, and then that the vast majority of them will be saved. Finally, those few that still reject God, along with those in the third resurrection (Rev 20:13), who had previously died after rejecting salvation, will all be destroyed in fire (Rev 20:15), turned to ashes under our feet (Mal 4:3).
That second general resurrection into the Kingdom is when the thief will be given his first chance at salvation. It is then that he will be baptized.
And, assuming the other thief hadn't previously accepted God's holy spirit and then later rejected it, he too will be there.