I really want to use the Elder Scrolls just as a jumping-off point for the discussion of fast travel mechanisms in general, but fast travel as a system seems to be one of the points people keep coming back to when talking about the changes over the history of the major TES games. To get my own prejudices out of the way: I like fast travel, except when I don't. Hope that's clear.
 
What I mean to say is, I like it when it bypasses what's basically a non-event, like the montage scene you might get in a movie where the characters walk through the mountains and you don't actually get to watch hour upon hour of them trudging through mud. When the exploration of an area is my objective, I don't use fast travel at all. When finishing a quest before I have to go to bed, I like to just zip there and get it done, since I use games as a way to feel more accomplished than I am in real life. The fast travel does NOT have to be easy, though. It's probably why I lean heavily toward Morrowind's system, which feels like it inhabits the world, instead of existing on top of it to make my impatient-self happy.  
 
A rundown of the systems used in ALL the main Elder Scrolls entries:
 

Arena's fast travel will probably be very familiar to players of Oblivion, strange as that may seem. Players are presented with a world map (click for a larger view) of ALL OF TAMRIEL, and there are major and minor cities connected by roads which you can click on and travel to. Nothing exists between the cities in real space; you can explore outside of the cities forever, but none of these outside-city-spaces actually meet up with other cities, dungeons, or towns that exist on the main map. All dungeons and buildings you find while exploring were procedurally generated, and all important places are accessible from the map.
 
When traveling you take a number of days, during which you spend a bit of money in inns. This may mean you don't finish a mission in time if the roads are bad due to weather, which happened to me at least once. Otherwise, there are no random encounters unless demanded by the quest or plot.
 

Daggerfall took procedural generation to a still-astounding extreme, putting all the points on a map in a real, connected space. You could stumble, in theory, across dungeon sites as you traveled, but the world was so massive, and largely uninteresting otherwise, that it was difficult to justify doing this. Fast travel was integral to getting anywhere, and could be done using a few sliders and buttons that dictated how fast you went, how much it cost, and if you would arrive at the destination during daytime or stumble into the place when the gates were still closed.
 
Players could own a mount which would reduce travel time, as well as a ship that you actually teleported to when you wanted to board it. It sat in the middle of the ocean, which was a little weird, but it acted as a house and a way to offset sea-going trip costs since it effectively followed you like a puppydog.
 
In addition to this, the fast travel spells of Mark and Recall were introduced, where you could mark a place that you could later travel to using the recall spell.
 

Morrowind had the most varied travel system of all, at least in terms of methods you could use.  Silt striders took you to mostly western and southern, inland destinations for a small fee; ships took you to ports in a mostly U-shaped curve of ports around the island; Mark and Recall were still used the same as they were in Daggerfall, and there were two new spells that would beam you to the nearest Imperial Cult altar or the nearest Tribunal Temple; and Guides would allow you transport to other mage guilds and, if you had the Tribunal expansion, to the walled capital city on the mainland.
 
Exploration on foot was much more practical in Morrowind than Daggerfall, although the mountains, the Ghostgate, and the seas often directed your line of travel, especially if you had a low level character. Swimming was still possible, if you didn't mind being bitten by fish and crab-men wherever you went.  
 
There were no mounts in Morrowind, and you could not purchase your own ship. One of the more effective methods of player-initiated travel on foot involved the use of jump spells and soul gems. Player encumbrance affected walking speed, as did player stats and spells.
 
Bugs sometimes caused the player to fall through the world, but unlike the abyss in Daggerfall these seemed a lot less deadly, even though Daggerfall's abyss bugs seemed to be prevalent only in interior environments.

 
Oblivion dispensed with most of this. Fast travel was now a player capability from pretty much the outset. Other than the cities, you still had to discover locations on your own, but you were allowed to effectively transport from one area to the next, consequence free, as long as you weren't over-burdened. Travel time is still computed based on player speed and route, so time-based quests may still run into problems if you take too long.
 
Unlike in the prior games, the player-character automatically regenerated health, so fast travel also acted as a way to heal up, rather than a way to get to a safe place to heal.
 
Traveling on foot in the relatively flat and road-heavy Cyrodiil is even more practical here, although some might argue less engaging.  Players also had the option to buy or steal a horse, hearkening back to Daggerfall, only the horse is fully realized with its own behaviors and ability to get creamed by aggressive locals. Traveling realtime also means that the character is subject to encounters, just like in Morrowind.  

 
Skyrim's methods are unknown at this time but seem pretty likely to follow Oblivion's lead, with instant fast travel to known locations. There's also at least a suggestion in one of the interviews that in-world fast travel options may also exist, but it didn't seem really solid when they were talking about it. Mountains will provide significant barriers that help to make travel less linear, but how this affects fast travel is unknown.
 
 --

What's remarkable to me about both Skyrim and Oblivion, and I've mentioned this before, is how close such a system actually feels to Arena. I am fond of Arena, and think that a more detailed and dynamic version of THAT game could be a nice dungeon-hacking time sink for me.  That said, it's interesting that you can, in effect, have a more Arena-like experience in the later games than with Morrowind.  For those who say it's been a steady decline, it really hasn't as far as I've seen. Morrowind was the peak of eccentricity with its completely in-world fast travel systems, forbidding the player to just zip there even if its location was known and had been visited prior. It forced the player to use a bit more ingenuity, which was organic and engaging, and at times painfully frustrating. Daggerfall and Arena were pretty much about beaming from place to place, and in Arena it was REQUIRED in order to experience the user-created world, with found dungeons and buildings being places to gather loot rather than having anything central to the game, whether by central you mean housing important artifacts, or actual quest locations, main or otherwise.
 
If we will, in future iterations, have a quest system that figures out where we've been and makes a new place for us to go, if we can explore the countryside and find things that aren't quite as interesting as the quest dungeons, and even less interesting than the hand-crafted main quest dungeons, what we have is a new, largely improved version of Arena. It seems that Morrowind, more than any of the other formulas here, allowed for players to willfully open up stuff they weren't ready for, and to find treasures that made them instantly rich or powerful in major dungeons, while both Oblivion and Daggerfall used the "loot roughly fits current character level" paradigm.
 
I guess all of this shows that the refinements haven't been a necessarily linear dumbing-down. For those who liked Morrowind's rough edges, you may have hit upon the pinnacle there, rather than mid-way down the slope into user-friendliness. 
 
--
 
In general, I'd say that fast travel is something that even pen and paper role playing games often have, where you can tell that the players are bored enough, or you know nothing will happen, that you can just say that time passes and you get back to more interesting things. The essay I'm still building up toward is a suggestion that the game itself must, at least in a rudimentary way, mimic the person running the game, and be able to tell what options are appropriate to maintain interest. Not just for fast travel, but for the game as a whole. I know, that's a tall order to ask, but I believe it's possible. 
 

Oh! While I'm typing, another one of my ideas for Skyrim: