I'm not sure if it different for each GC but there was an NPC with a quest in Camp Tranquil that allowed you to get your battle chocobo.