This is going to be a significantly long journey.
I'm not sure if your party realizes just how far it is from The Dalelands to Waterdeep. For reference, it's roughly 1,200 miles as the crow flies. Unfortunately, however, there is no direct travel route that takes you on a straight line from Shadowdale to Waterdeep. There's the Desertsmouth Mountains, the Marsh of Chelimber, The High Moor, the Serpent Hills, and even the Anauroch Desert, all of which would have to be passed through or circumvented, so we'll probably want to take a roundabout route.
Disclaimer: all distances are approximate. I have a huge poster map of the sword coast on my wall that I took down and measured these distances with a ruler, but these are still only approximate distances. The edition that the map represents should be mostly irrelevant, as the overall topography of the land hasn't really changed
The Means of Travel
The first things we want to figure out is what the fastest means of travel is, so we know which route to take, or when to switch means of travel should one option become unusable. For travel method, we have several options.
Land Travel: A normal travel pace is 24 miles per day, which assumes 8 hours of traveling per day at a pace of 3 miles per hour on a road. Travelling through the wilderness would likely decrease this pace by some margin, so we'll prefer sticking to roads. We can increase our pace to 30 miles a day, but then we take a -5 penalty to Passive Perception, making encounters more likely, or we can slow our pace to 18 miles per day, but allowing us to use stealth, and make encounters less likely.
Water Travel: There are a few types of boats that we can travel on, each with different speeds. If the characters have enough funds, they could buy passage on a boat, though this would likely be quite expensive because of the distances we need to travel. Alternatively, they could work for their passage as sailors and mercenaries defending the boat in case of pirate attacks. The main advantage of boats is, they keep moving even when part of the crew is resting, effectively giving them round-the-clock movement. Obviously, the faster boats would be preferable, but availability of boats in port will be up to you as the DM. For boats we have
- Galley: 4 MPH or 96 miles per day
- Longship: 3 MPH or 72 miles per day
- Warship: 2.5 MPH or 60 miles per day
- Sailing Ship: 2 MPH or 48 miles per day
- Rowboat: 1.5 MPH or 36 miles per day - a bit faster than fast-pace travel
- Keelboat: 1 MPH, or 24 miles per day - about the same as normal pace travel
These are going to be the two main types of transportation available to the players, anything else will likely be too expensive. Since boats are obviously the much faster option, we'll want to stick to them whenever possible. Unfortunately, no single waterway connects Waterdeep to the Dalelands, so some land travel is unavoidable. With this information in mind lets take a look at possible routes.
Luckily for us, we can at least start our journey on the water, as Shadowdale lies on the River Ashara, a rather large river that can accommodate even the largest of ships, allowing us to get a decent start on our journey, jumping onto a ship right off the bat. We'll take it down to Scardale, on the coast of The Dragon Reach, which is the Northernmost portion of the Sea of Fallen Stars, in a journey of about 500 miles. One there, we'll look for a ship headed for the city of Proskur on the Westernmost edge of The Dragonmere, the farthest west portion of the Sea of Fallen Stars, another 900ish miles.
We disembark at Proskur, and from here start the first (and hopefully only) land travel portion of the journey. We take the Road 150 miles west to the City of Irieabor, which lies on the shores of The River Chionthar. The river over 700 miles of land, all the way to The Sea of Swords, and passes right past Baldur's Gate, which, assuming that that's as far as our current ship is travelling will be where we book out final voyage, a mere 550 miles to the city of Waterdeep.
So, we're looking at a grand total of about 2,650 miles of sea travel, along with about 150 miles of land travel. Assuming a common sailing ship for each stretch of water travel, and a normal pace for the land travel, we're looking at a travel time of about 55 days of sea travel, 6 more days of land travel, and possibly a few additional days here and there waiting for a ship to be available that's heading in the right direction. All told, we're looking at somewhere along the lines of just over two months of travel time.
Other Means of Travelling
A few more travelling options that I left out from the main I will list here, for completeness.
Teleportation magic: Either Teleport or Teleportation Circle will get you to Watedeep in quite literally an instant. Considering some of its denizens, and the fact that many major temples and guilds will have permanent circles, you're quite literally guaranteed that there will be a teleportation circle to target, though those circles may not be in the safest locations, and may constitute the parties first adventure in the area! The main preventative, of course, is learning the sigil sequence to one of those circles, and then working up enough money to pay someone to teleport them there, or enough levels to do it themselves. The cost market standard cost for getting someone to cast a level 5 spell for you (based on the cost for Raise Dead) is roughly 750 GP plus the cost of any components that are consumed by the casting (in this case, 50GP worth of special chalks), although some spellcasters, may instead offer to cast it for them in exchange for the party performing a task of the casters choice (read: do a quest). The head of one of Myth Dranors temples might offer the use of his temples circle to travel to their sister-temple in Waterdeep, in exchangfe for investigating some recent goings-on in the surrounding forest. Since Myth Dranor is just a few days travel from Shadowdale, this could cut down on the total travel time by more than 90%! Considering that this is a party of adventurers, working up the 800GP required to get someone to cast Teleportation Circle to get us to Waterdeep might actually take less time than travelling there by boat.
Airships: The other, final option, is air travel. I leave this one for last since it's the least likely to become available to the players as an option. A standard airship, like the one from Storm Kings Thunder, travels at about 8 miles per hour, and like the water ships, it can travel constantly, instead of needing to stop after only traveling for a small portion of the day. This gives it a travel rate of a whopping 192 miles per day. If it happens to catch a tail wind, it gets boosted to 12 miles per hour, or a truly rapid 288 miles per day, although with a headwind, they'd be slowed to the same pace as a galley, 4 miles per hour. This means, however, that they could be to Waterdeep in just 5 days with a strong tailwind, or worst case scenario, just under 2 weeks with a strong headwind the entire journey. Like I said, though, this is the least likely for them to have access to, both because airships are exceedingly rare, and because chartering passage on such a ship would be prohibitively expensive for low level adventurers.