You don't have to do anything secret to get Terra. You go the the town the first time and she refuses to join back up because she wants to stay with the children. Then you continue on and come back later. That's it. I usually come back just after I get the airship and she joins up.

Shadow either dies on the floating continent or does the suicide dance in the tower. Either way it's all over for him in the end.