A chocobo trade makes the most sense. I'm willing to bet via black chocobo is how Rosa got to the town of Kaipo in the first place!