I think we don't necessarily need a mode of transport.
If we have say:
Town A []___
\____[] Town B
And the player presses right, we could have the character automagically walk there, or snap to the location on the world map.
I think the player should have freedom to revisit any previously explored locations, provided the story allows for that.
I think progression could be established in a mixture of two ways:
Town A []___+_____+
\+____\_[] Town B
Have certain crossroads at points in the map and put "roadblocks" on them.
Have enemies or temp battles in these transitional areas, the player must clear one of two paths to reach town B. Once Town B is reached, all other "roadblocks" are cleared for that area. Or, simply use the former method described above, without crossroads, and in some instances maybe without roadblocks as well.