Das ganze nochmal in ausführlich:
Du musst zu einer Stadt im südöstlichen Eck der Weltkarte. Lege dort an, und betrete die Stadt. Nach einer kurzen Szene begibst du dich auf der Weltkarte zu dem Chocobowald südwestlich der Stadt. Fang dort den Chocobo und flieg zurück zur Ancient Library und rede mit Cid. Der Rest sollte sich von selbst erklären.