Fantasy Trek Campaigning

Starting scenario: Start with a large island/small continent isolated from the rest of the world, possibly by some horrendous godswar or magical catastrophe or the fall of the big connecting empire. Now, years later, the rulers of this island want to know what else is out there and so  commission a ship and begin recruiting a crew. The long term goal is to journey to the capital of the previous world-spanning empire and find out what has happened and what is going on. Armed with some old maps and rumors from fishermen and local travelers (and perhaps aided by some scrying magic) the group sets out to what should be a relatively nearby land that was friendly in the past and might have maps of the rest of the world.

The first obstacle is to come up with a reason that your starting location a) doesn't know what's going on in the rest of the world and b) wants to find out. Maybe it's not a government, maybe it's the Mages Guild or a Merchant Guild of some kind, or an individual mage or sage or merchant. If you need a real world model think of Brtiain after the departure/fall of Rome. It never was the center of the empire and after a few decades detailed knowledge of the rest of the world would be fairly scarce. It might even be a plundering expedition - some Viking lord invades Britain sacks a church and finds some information about Rome and decides to outfit an expedition to go sack it! This would be hundreds of years after it has fallen - but he doesn't know that! 

There is also a need to determine what character options are available. I would probably let the player choices drive some of this. If I end up with a party of gnomes, drow, and halflings then those three races are players in the homeland. If you're talking about a place at the far end of the world then the exotic stuff makes sense anyway.

The players should have some limited information about the world  - old maps work for me - as your party needs an idea of which way to go and what their options are. You can still change things up, but it's good to give them an outline of what might be out there. 

This is also a great campaign to break out the random encounter tables and the weather charts if you don't typically use those. Even the planes have some kind of weather - introduce your players to it.

I do think that some kind of "ship" is needed for this kind of campaign. Without a ship you have a a series of footslogging quests or an army on the march. With some kind of mobile base, the party doesn't have to carry a bunch of supplies on their back and has a place to run to when they're in trouble. It's one of the things that makes this kind of game different and I would think carefully before doing away with it. 

Not strictly fantasy but you get the idea if you've seen the show

For a fantasy campaign I also like the idea of giving them a goal beyond pure exploration. Giving them a quest - to find the old imperial capital or to track down some old hero or maybe even the previous expedition sent out a few years ago that never returned - gives some focus to the campaign and sets up a "story" if you want to make it one. There's a natural arc to it at least - traveling to the goal finding it/exploring it, and then traveling home. The story of the Argonauts tends to focus on the "finding it" while the Odyssey is all about the "going home" part, but there's no reason your campaign can't cover both.

Once it starts you have an open ended campaign that is largely player-driven. If things get too quiet there's always a chance that an evil humanoid race is taking an interest in exploring the area as well - maybe seafaring hobgoblins have developed their own civilization out there and start showing up in the explorations and random encounter tables. 

Alternate Approach #1 (from an post of my own a few years ago):

After reading through the Manual of the Planes, a short scan of The Plane Below, and reading through some of the published paragon and epic adventures a certain theme began to coalesce in my head. Call it..."Plane Trek". I would start the campaign at 11th level - PC's can be from any campaign world, any race, any class, etc. They are heroes on their home world, at least in their village/city/kingdom. They are then recruited into an organization based out of Sigil (most likely) that explores the planes and deals with threats that involve more than just one world - the Big Threats. The organization sends them out on planar ships to explore, map, and deal with these kinds of threats. I'm not sure how formal to make the organization - more rigid command structure and ranks or more loose almost like a pirate crew. If I could keep it somewhat episodic - this week the ship has detected an astral dragon heading for a githyanki fortress and is moving in to investigate - then it would make it very easy to drop in onetime players in a sort of sandbox, sort of mission-based delve format. At paragon they would be the lesser officers on the ship but once they hit epic they would be the "bridge crew" and in charge of their own travels in a big way.

Alternate Approach #2 

Flying Boats - this approach removes the need for big areas of water and makes enough sense in higher magic worlds that your player shouldn't mind. It also explains why the players are out there on their own - "hey we can only afford to make a few of these things" - and why it's an especially good idea to keep the ship intact - you can build another watercraft easily enough but you're probably not going to build another flying ship from scraps.