Traveling is done several ways in this game. Anything from walking to sailing your own canoe.
Walking - Slowest. Random number is generated each time you enter the outworld, and when it reaches Zero, you fight. Each step you take has a value, plain grass being -1, forests -3 (or so), etc. While the Enemy type is predetermined, how you fight it is not. Reverse battles are caused by overshooting the Zero by a certain number, and conversely, if you hit Zero exactly, you will catch the enemy by surprise. These values also effect how many of a particular enemy you face, but it is unclear to me how. On an even trickier note, it seems that if you stop and heal your characters one step before an enemy encounter, the countdown is reset.
White Chocobo - Average Speed. Chocobo's are found in forest areas, often in trees formed into a small circle. You won't fight enemies while riding one, but when you disembark, the Chocobo will automatically run back to its home forest. Chocobo's can walk through rivers, plains, forests, and deserts.
Sailing Ship - Average Speed. The ship is obtained by returning the dragon eye to the Nepto Temple; The Vikings will give it to you in gratitude. The ship can sail through ocean water only, but unlike previous Final Fantasy I, you can disembark at any shoreline.
Canoe - Slow. The Canoe allows you to journey through rivers and lakes, and is automatically carried during your journey once you obtain it from the King of Sasun. Unfortunately, the waves of the ocean prove too rough for it.
Cid's Airship - Average Speed. The Hikuutei is found in the desert west of Kazus. It can go over any surface but mountains. It can only land on grass plains, and is eventually used as a wrecking ball (of sorts). Enemies are not fought in Airships unless in special areas.
Airship Enterprise - Above Average speed. The enterprise is actually a modified version of the Sailing Ship, using a part from the Floating Fortress. This airship can go over any surface except mountains, but can only land in the ocean. Enemies are not fought in Airships unless in special areas.
Airship Nautilus - Super Fast! The Nautilus is created by the Scholar's guild in Salonia after they accidentally shoot down the Enterprise. Like the other airships, it can not go over mountains, but instead can submerge under the ocean water to find secret caves (once modified by Dorga's magic spells). The Nautilus can only land on grass plains. Enemies are not fought in Airships unless in special areas.
Airship Invincible - Average Speed. The Invincible is the Battleship of of flight. It is 4 times the size of the nautilus! In case you have an Airship battle (in special areas), the Invincible is armed with a cannon that hits all enemies before each round begins. You can disembark on any form of land (excluding mountains) because the ship never actually lands! Inside, the ship contains a free bed (Inn), 4 vending machines (Item, Weapon, Armor, and Magic for sale), and a strange white bin. Deposit a carrot, and the infamous Fat Chocobo will appear, complete with his trademark music! Also, while driving the Invincible, if you press the "A" button, the engines will temporarily increase power to lift you over thin sections of mountains.