You have to wait and he appears with five seconds to spare if you're at the very edge of the floating continent where you can see the Blackjack below. Then, in the World of Ruin, he'll be in the Veldt Cave.. the funny thing is, in the Japanese version, I don't think Shadow was supposed to survive. Or the Americans translating didn't do a good job of it as it says, "SHE" in reference to Shadow when you find him there in the cave. And, if you didn't wait, Relm is there instead in the cave. :)

You end up taking Shadow back to Thamasa I believe and then you have to bet a weapon called the Stryker at the Coliseum and you will fight Shadow. He's super easy to defeat and then you speak briefly to him and he comes with you.