Take the mysterious fossil to in Menethil Harbor.
This fossil bears a striking resemblance to one I once saw in Ironforge. An archaeologist by the name of Flagongut brought it to our annual Explorers' League conference. He believed the fossil had a power which could be unlocked somehow.
Last I heard Flagongut had holed up in the Deepwater Tavern in Menethil Harbor, awaiting escort to the Whelgar Excavation Site. Seek him out and show him Remtravel's fossil. Perhaps he can reveal the secrets of the past.
What ya got there, friend?
Oh my! You say this came from the distant lands of Kalimdor?
Amazing! Simply amazing!
The quest text says that the ship to Menethil departs from Stormwind, but in fact the ship to Menethil was replaced by a ship to Valiance Keep with the release of World of Warcraft: Wrath of the Lich King.
Sept 6, 2009: The quest text actually says nothing about a boat. Instead, it says "Good luck findin' your way there!"
June 7, 2010: Although there is a flight that runs between Menethil Harbor and Ironforge, you can waste a tremendous amount of time trying to take the boat from Auberdine to Stormwind and then the tram to Ironforge, only to find that the flightmaster at Ironforge won't fly you to Menethil unless you've already been there and visited the flightmaster.
The overland route is evidently a challenge for a lower level player. A suggestion from the comments at WoWHead is to ask a mage for a portal to Theramore and then take the boat from there to Menethil.
There are numerous YouTube videos of overland routes from Stormwind to Menethil, such as this one which the poster claims took only seven minutes. See that video's page for links to other videos which claim even shorter routes.
Another possibility might be to take a flight from Auberdine to Theramore but as with the flight from Stormwind to Menethil, some other travel method may be required to acquire the flight plan for this route.
Yet another way to get to Menethil for the first time might be to take a boat from Stormwind Harbor to Valiance Keep in Northrend and then make your way all the way across Northrend to Valgarde, where you can take another boat to Menethil Harbor. According to the Northrend Map at MapWoW there are flight routes connecting Valiance Keep and Valgarde. One possible route might be Valiance Keep to Stars' Rest to Wintergarde Keep to Westguard Keep to Valgarde. (This route is based on WoW Wiki documentation for these locations. The map does not show a direct route between Stars' Rest and Windergarde Keep, so a stop at Moa'ki Harbor might be necessary.) Overland travel might be required to discover some or all of these flight routes for the first time.
See Transportation for specifics about the boats that run between Auberdine, Stormwind, and Valiance Keep, and between Menethil Harbor, Theramore Isle, and Valgarde.
July 4, 2010: The simplest way to get to Menethil Harbor is to make your way to Ironforge (get to Auberdine, take boat to Stormwind, take tram to Ironforge), head into Dun Morogh, follow the road east into Loch Modan. From there you just take the road north through Dun Algaz into the Wetlands, and follow that road north and west straight to Menethil Harbor. It's simply a matter of staying on the roads, even a brand new character can make it there, though it would take awhile without a mount.