I've reached Pulse, and I know there are Chocobos around here somewhere. How can I unlock them?
As Kevin Y said, you need to unlock then beat mission 14 to unlock the chocobos, which requires you to beat 13...this is the chain:
1->2->3->5 and 7->12->13->14. The link has all the location maps for the Bosses+Cieth Stones.
After you beat 14 you will find Chocobos scattered throughout the Archelytte steppes. Hope this helps.