Ok, here's a thorough walkthrough that i think helped me a lot on getting them. i had the same problem u are.
Ok! find a lady in the Calm Lands that says "Lost? Follow me to go back to Bevelle.". Follow her, she won't actually go back to Bevelle, she'll either go to the center part where the save sphere is, or near the path that is far south. When she stops moving, talk to her again. And just keep talkig to her. After she repeats herself lots, or walks off the screen. Go to the center area(if not already there), and there should be a lady on a chocobo. Talk to her and u can train chocobos. Once you've completed all the stages in training, u can ride one of hers.
Hope that helps.