Although it's slow, boring, and makes your feet hurt, walking is the main mode of transportation between towns in the beginning of the game, and the only form of travel in towns and dungeons. While traveling on foot, you'll face random encounters constantly (which are necessary for building EXP and G). Chocobo's unfortunately weren't introduced until later in the series, so walking will have to do.

In Pravoka, you'll meet Bikke the Pirate. Bikke is up to no good, looting and plundering and whatnot, and his Mates have taken over the town. If you kill Bikke's Mates, he will chicken out and give you his ship.

The Ship is a very fast mode of transportation. It is far faster than walking, in most cases. While aboard the ship, you will have to fight random battles with the likes of Sahags and Sharks. The Ship can travel the open seas, but it cannot sail up rivers. It can fit underneath the Bridge north of Coneria, though. The only place to get off of the Ship is at a dock (which are located throughout the world near towns), or at the mouth of a river (once you get the Canoe).

After defeating Lich, the Fiend of Earth, one of the Sages in the Circle of Sages at Crescent Lake will give you a brand new Canoe. This is used first to travel on rivers. With the Canoe, your party can reach many places that were previously inaccessable. Also, once you acquire the Canoe, you can dock your Ship at the mouth of any river. When in the Canoe, you will face random encounters with strong enemies like Hydras and Ochos, so be careful.

Aaaaaaaaahhh. Good old Airship. The Airship is the best way to travel. Although there were many Airships in the world in the past, only one remains, buried under the desert. You must use the Floater from the Ice Cave to raise the Airship from the desert if you are to travel to the lands to the north.

The Airship is the fastest way to travel; it's about four times faster than walking. It can fly anywhere, even over mountains. But it can only land on grasslands or open fields, so there are still some places that you cannot access easily even with the Airship (the Castle of Ordeals, and Lefein, for example). In the Airship, you'll face NO random encounters, which is great later in the game when random encounters become useless and boring. On top of all that, flying the Airship is lots of fun. You can fly around the world a couple times, or try to land on top of castles, for starters. Just have fun with it.