When you're fleeing on the floating continent, after the "battle" with Kefka, when you get to the spot where it says that the airship is below and do you want to jump, select "No" (it might be "Wait" or something like that). When the timer reaches 5 seconds, Shadow will show up and you'll leave Floating Continent with him.