The Warrior of Light is given an airship pass early on in the MSQ's just before they are sent to visit each of the three main city states. The RDM quests also involve dealing with a vessel travelling between two ports - and despite there being cause to be suspicious of it there is mention of all the necessary documentation being in place which prevents the authorities from simply seizing it.

There's countless references to documentation in both the MSQ's and side quests. You can even get your hands on identification papers for chocobo breeding if you tackle it in The Gold Saucer.