mors tua vita mea
Shadow is a tough character to get in your party -- just when you think he's joined you for good, he ups and leaves! He will only join up with your if it's to his advantage or if you're willing to part with a little cash... well at first, anyway. I've outlined all the different places you can encounter Shadow, and how you can get him in your party each time!
The first time you see Shadow is in the Cafe in South Figaro. As you enter the building, the music shifts to Shadow's theme song -- a clear indicator that the mysterious man sitting at the table is of some significance. If you approach him, Edgar will point out that his name is Shadow and that he's a notorious assassin. If you try to get him to join the party, he will simply tell you to go away (and he'll even add the friendly tidbit that his dog eats strangers). Looks like you won't get him this time...
When your party gets divided in two (after you've visited the Returner's hideout), Sabin will wash up on the shore next to a house. Enter, and you will come across Shadow. Shadow will explain to Sabin that the only way he can get where he wants to go is through Doma, and he offers to join forces with Sabin (but he warns him that he can leave at any time). That was pretty easy! Shadow may randomly leave the party, and there's not much you can do about it, but he will usually stay until you reach Barren Falls. At this point, he will leave no matter what. Clearly, you're crazy to be jumping down a waterfall...
The next time you will encounter Shadow is in Kohlingen at the Cafe. If you have four members in your party, he will tell you to go away. However, if you only have three in your party (you have the option in Narshe to select your party... only pick three members, you don't have to pick four), he will offer to join you for a fee of 3,000 GP. He will stay with you through the end of Zozo. As your party disembarks, he tells you that he is no longer of any use and takes off.
Guess who's back? General Leo tells the party that he hired someone in town to accompany you, and it just so happens to be Shadow. When you approach him, he tells you that he is working for the Empire, but he will not "garrote" you. After visiting Thamasa, saving Relm, and a whole bunch of other stuff, Shadow leaves the party again, saying that he'll search for espers his own way. Even though Shadow was only in the party for a brief period of time, he gets more dialogue in this section than any other.
You will see Shadow laying on the ground. Go talk to him -- he's pretty pissed at the Empire, so he'll offer to join you (now he wants revenge). He will stick with you until after the battle with the Atma Weapon, at which point he leaves again. Once the continent begins to fall, he will come back and distract Kefka, thus allowing the party the escape. Once you reach the airship, wait for Shadow. He will show up with five seconds remaining. If you don't wait, he will die, and you won't be able to get him back in your party in the World of Ruin.
World of Ruin
When you enter the Cave in the Veldt, you will see Interceptor run off. Eventually, you will see Shadow laying on the ground, badly wounded. After fighting a boss, take Shadow to go recover in Thamasa. He will tell you to leave -- Interceptor is standing guard. Yep, you guessed it -- your quest to recruit Shadow isn't over just yet! If you go back to check up on him in Thamasa, a village will tell you that he has gone to the Colosseum. So make your way over to the Colosseum to recruit him for good! Wager the Striker (which you found in the Cave in the Veldt) in order to fight Shadow. When you win (it should be really easy), Shadow will join you permanently. Yay! Sometimes you just have to work hard to get what you want...