Note: This guide is not meant for power-leveling purposes. Rather, it is meant to show a player the most efficient way to complete all quests available for a particular zone. If you know of a better order or method to accomplish this, your input is welcome (in fact, greatly desired). For major changes, feel free to edit, but make a note in the talk page as to your reasoning.
Kessel will give you an Elekk speed buff for 15 minutes, avoid getting it into water or into buildings, also stay out of the Stillpine Hold cave. Otherwise you'll auto-unmount and lose much time. It is possible to stay mounted while talking to NPCs, however you must be almost right on top of them to do so. Druids: You won't get the speed buff if you're in bear or other form.
Ride back to Azuremyst. The objective NPCs for  The Kessel Run don't have extra quest marks on them, talking to them is enough to get the quest updates.
First stop is High Chief Stillpine at Stillpine Hold. Just talk to him for  The Kessel Run, but also accept  Warn Your People (which is only available when you did all other Stillpine Hold quests but this, otherwise just ignore this step).
Then ride on to Azure Watch. Talk to Exarch Menelaous and also turn in  Warn Your People.
Final stop is Odesyus' Landing. Talk to Admiral Odesyus to complete  The Kessel Run and then ride back to Kessel's Crossing (63,87) on Bloodmyst Isle.
Ride northwest to Blood Watch. Restock food/drink; sell loot; mail stuff and otherwise free up space. Bind your Hearth Stone to Blood Watch, also get the flight path! Accept quests as above.
Head due east from the Inn and you will soon find a Blood Mushroom (right click to obtain). Head slightly southeast until you reach Wratchscale Lair. Head up the path to the upper level and then kill Lord Xiz. Once he is dead, be sure to also right click on the Draenei Banner in your inventory to run it through his corpse to complete  Declaration of Power. Pick up a Ruinous Polyspore on the way.
From now on, look for Sand Pears, which are at the base of the Trees. Go southwest to discover the area of the Bristlelimb Enclave. While here, at the east side of the Enclave, you will see Princess Stillpine locked in a cage. Talk to her for  Saving Princess Stillpine (assuming you can talk Furbolg, otherwise just skip this quest). Head northwest to the camp here and kill the Furbolgs until High Chief Bristlelimb appears. Kill him and be sure to get his Key. Then return southeast back to Princess Stillpine and right click on the lock to free her. Finished collecting 10 Sand Pears.
Head northwest to The Lost Fold. You should see a red-colored Impact Site Crystal here. Go to your Inventory and right click on the Crystal Mining Pick to collect the Impact Site Crystal Sample. Swim through the blood river to the northwest, pick up an Aquatic Stinkhorn in it, then go west to you'll find the last mushroom, a Fel Cone Fungus.
Head west from Kessel's Crossing along the coast and you will soon discover the area of the Blacksilt Shore. To tag the Blacksilt Scout Murlocs, you cannot engage them in battle. You will have to get close enough to them though to right click on the Murloc Tagger to tag them. Work your way west and back east again along the shore until you have all 6 Blacksilt Scout Murlocs tagged. While on the beach, you will also see a Murloc named Cruelfin. Kill him and be sure to get the Red Crystal Pendant from him, which will start  Cruelfin's Necklace.
Return to Blood Watch. Turn in the quests and get followups as needed.
Visit your class and/or profession trainers, learn the new skills, then get back out of the Exodar and turn in  Hippogryph Master Stephanos at Stephanos. Get the followup  Return to Topher Loaal. Take the flight back to Blood Watch, and turn it in at Topher Loaal at the Blood Watch inn.
Head northeast from the Blood Watch until you see a large building complex, the Ruins of Loreth'Aran. Kill the Naga enemies until you can talk to the dead Draenei Cartographer at the southern building for your reward. You will then get  Salvaging the Data. Kill Nagas until the Survey Data Crystal drops.
Move west until you find Sunhawk Spies in Bladewood. Kill the Sunhawk Spies in this area until you have all kills needed. Return to Blood Watch.
Turn in completed quests and get followups. If you already have 10 Irradiated Crystal Shards, then get the quest  Irradiated Crystal Shards from Vindicator Boros and turn it in, which will unlock the repeatable quest  More Irradiated Crystal Shards, where you can turn in stacks of 10 more shards for some nice litte buff stuff.
Leave Blood Watch, heading southwest. Kill Corrupted Treants you find on the way until you have all 6 Crystallized Bark.
Take the road until you reach Nazzivian. Continue west for a little ways and you should soon see a large shrine off to your right. Work your way there and then right click on the Nazzivus Monument Glyph to obtain it in your inventory. Find Tzerak (he patrols west of the monument), kill him and loot Tzerak's Armor Plate for  Signs of the Legion.
Continue killing the Satyrs and Felsworns as needed to complete the quest. Hearthstone to Blood Watch. Turn in completed quests and get followups.
Leave Blood Watch to the northwest, until the road forks. You will find the Elder Brown Bears and the Mutated Constrictors (these enemies can be found in quite a large area just south of the Bloodwash, even as far south as Bladewood). Kill these enemies until you have all 14 Vines and Bear Flanks.
Pass Axxarien to the east. When you reach the coast, find a large dead Turtle on the beach (42,21). Kill the Murlocs near this Turtle so you can talk safely with Clopper Wizbang for your reward. He will then have  Pilfered Equipment and  Artifacts of the Blacksilt.
Kill the Blacksilt Seers until you have all 3 Crude Murloc Idols. Also kill the Blacksilt Warriors and Blacksilt Shorestrikers until you have all 6 Crude Murloc Knives. At the first set of Huts to the west of where Clopper Wizbang is located, you will find a crate at the middle Hut marked Clopper's Equipment. Kill the Murlocs guarding this crate and then right click on it to obtain in your inventory.
You should be put to handling Deathclaw. He can be found at the far west end of the Bloodwash by the Waterfall. Kill him and be sure to get his Paw. Then continue on the murlocs heading back east.
Once you have the Paw, Idols, Knives and Clopper's Equipment, you can first go back to the Turtle Shell and talk to Clopper Wizbang for your rewards. After getting your rewards, you can right click on the Weathered Treasure Map for  A Map to Where?.
Move east until you reach The Warp Piston, walk near the entrance to get the Portal Site discovered message. While you are here, kill 5 of the Void Anomalies.
Kill a path to the Ruins of Loreth'Aran southeast near The Crimson Reach beach. At the northern building, you will see a small ramp heading up to the 2nd Level. Here you will see on the ground a Battered Ancient Book. Right click on this Book for your reward. You will then get  Deciphering the Book.
Hearthstone or travel back to Blood Watch and turn in quests and get followups.
Leave Blood Watch to the west, heading to the Cryo-Core. Kill the Royal Blue Flutterers until you have all 10 kills.
At the Cryo-Core, kill the Sunhawk Reclaimers in this area until you have all 12 Medical Supplies (there are also Medical Supplies that are lying around that you can right click to pick up as well). Work your way inside the Cryo-Core and you will soon see Galaen lying dead on the ground at the northern end. Right click on Galaen for your reward. You will then get  Galaen's Fate Also, lying next to Galaen's Corpse is Galaen's Journal. Right click on this Journal for  Galaen's Journal - The Fate of Vindicator Saruan.
Continue to kill the Blood Elves in this area until you find the Jeweled Amulet (this may take a while to obtain as it seems to be a rare drop) and also finished collecting your 12 Medical Supplies.
Travel back to Blood Watch and finish your 10 Royal Blue Flutterer kills on the way.
Once arrived back in Blood Watch, turn in the quests and get follow ups
Head north on the main road from the Blood Watch and at the first fork in the road, head due northwest to discover the area of Axxarien. Kill the Axxarien Shadowcasters and the Axxarien Hellcallers until you have all 10 kills (5 of each type). While doing do, right click on the Corrupted Crystals until you have all 5 in your inventory.
In the northeast corner of this area are both a large Shrine and a large Crystal. At the Shrine is the Leader named Zevrax that you also need to kill. After killing him, right click on the Crystal Mining Pick at the large Crystal near Zevrax to obtain an Axxarien Crystal Sample.
Then move southwest until you find Vindicator's Rest and turn in  Talk to the Hand at Scout Jorli.
Head north until you discover the area of The Foul Pool. Kill the Fouled Water Spirits in this area until you have all 6 kills.
Jump down the red-colored waterfall. Swim until you are right under the waterfall and then right click on the Water Sample Flask to get the Bloodmyst Water Sample.
Hearth to Blood Watch and turn in quests and get followups.
Once you accept this quest, you are transformed into a female Blood Elf. Then go and talk to the Captured Sunhawk Agent in the Makeshift Prison using the Talk Bubbles until you get a yellow message that you have successfully recovered the Sunhawk Information. Then return back to Exarch Admetius for your reward. He will then have  Vindicator's Rest.
Repair, sell loot and restock, etc. Be especially careful as this will be a long circle.
Leave Blood Watch, travel back towards Vindicator's Rest. You should spot Matis the Cruel along the road. Don't kill him! If you see him, quickly go to your inventory and right click on the Flare Gun. When you do so, a Tracker ally comes to help you. If you get Matis the Cruel's health down enough, you will get a yellow message that you have successfully captured him (note that this seemed quite easy).
Just south of Vindicator's Rest, you can find the Enraged Ravagers as well as the Mutated Tanglers. Kill the Enraged Ravagers and the Mutated Tanglers until you have all 18 kills (10 Ravagers and 8 Tanglers and note that you may have to head slightly southwest a bit to find more of these enemies).
Continue southwest and you will find the Sunhawk camps. Kill the Sunhawk Pyromancers and Sunhawk Defender enemies until you have all 20 kills (10 of each type). If at all possible, kill these enemies at the most southern camp (see your World Map), so that you can get to the Pool area south of this camp. Once you reach this Pool, swim under the water and kill the Void Critters until you have all 12 kills (you will probably have to wait for a respawn to get all 12).
Now head north, finishing your 10 Defender and also 10 Pyromancer kills on the way. Avoid aggroing the elite mobs guarding the Vector Coil.
After this, head west from the Foul Pool to discover the area of Amberweb Pass. You will see off to your right by the edge of the mountain Researcher Cornelius who has  They're Alive! Maybe.... Fight your way up the Amberweb Pass.
Kill the Myst Leecher and Myst Spinner Spiders in this area until you have all 16 kills (8 of each type). As you do this, you will also see many Cocoons. Range shoot these to free the Expedition Researchers. Be warned that there are also other enemies in some of the Cocoons.
Work your way up the hill going northwest here until you reach the top (see your World Map if needed). Up at the top you will find the boss Spider named Zarakh surrounded by many other spiders. It is highly suggest taking out as many of the smaller spiders first as possible and then taking on Zarakh one on one. Work your way back down the mountain, finishing the other kills you might still need before returning to Researcher Cornelius and turn in  They're Alive! Maybe...
Repair, sell loot and restock, etc. Be especially careful as this will be another long circle. You might want to make a trip to the Exodar and learn your spells. Also if you are a skinner, considered going there for Journeyman Skinning, because of the upcoming dragon whelps.
If you quested at Odysseus' Landing in Azuremyst, go to the Mailbox and retrieve A Letter from the Admiral. Right click on this Letter for  The Bloodcurse Legacy. If you skipped that quest series, you'll have to visit Admiral Odysseus in Azuremyst and you might be able to accept  The Bloodcurse Legacy there.
Leave Blood Watch heading northeast, stop at the southern part of the Ruins of Loreth'Aran. Just to the south of where the dead Draenei Cartographers are found, find the Mound of Dirt and turn in  Nolkai's Words. Right click on Nolkai's Box for Nolkai's Band and other goodies.
After this, swim northeast to the larger island off of the eastern coast to discover the area of Wyrmscar Island. Find Prince Toreth at the southern end of it. Accept  Restoring Sanctity
Head to the eastern shore of this island and you will soon find Captain Edward Hanes standing by a ship off of the coast. Talk to him for your reward. He will then have  The Bloodcursed Naga. He then casts a spell on you that allows you to swim faster and breathe underwater without having to worry about your air supply. Now head east into the water here to discover the area of The Bloodcursed Reef. Kill the Bloodcursed Naga in this area until you have all 10 kills and then return and talk to Captain Edward Hanes for your reward. He will then have  The Hopeless Ones....
He will then cast the same spell on you for swimming faster and breathing underwater. Swim out east a ways. Head to the sunken ships at (83,12), (83,22) and (81,29) for Bloodcursed Voyagers and loot their Bloodcursed Souls. Then swim west back to Captain Edward Hanes, but DON'T TURN IN  The Hopeless Ones... yet!
Instead, ask him to renew the waterbreathing and swimspeed buff (Can you cast the spell to help me breathe and move underwater?). Swim back to the main island to collect 8 Dragon Bones.
Move to the top of the hill. Clear it of the whelplings and prepare to fight. Then right click the ever-burning pile and wait for Razormaw to descend. Some hints for the battle:
His flame breaths can be interrupted.
He can be feared and stunned.
Don't forget a Draenei's Gift of the Naaru.
Once he's dead, return to Prince Toreth and turn in [21G] Razormaw.
Visit Captain Edward Hanes, renew the swim buff, then get the rest of your 4 Bloodcursed Souls if needed and before turning in  The Hopeless Ones.... Renew the buff again (can't do it anymore after completing that quest). Turn in the quest and get the followup  Ending the Bloodcurse.
Swim south until you reach the Bloodcurse Isle. From the north side of the Isle, work your way up the path to the top. Clear out the area here and ensure you're at full health and mana before you right click on the Statue of Queen Azshara to summon Atoph the Bloodcursed. Kill him and then swim north back to the Wyrmscar Island and talk to Captain Edward Hanes. Turn in  Ending the Bloodcurse. Whelplings are useful for grinding here.
Hearth back to Bloodwatch and turn in quests and get followups.
If you're not a Draenei, you can accept only The Sun Gate, so just skip what you must.
Repair, sell loot and restock, etc. Fly to The Exodar, learn your new class spells and if you want, do your class quests if there are any new, then fly back to Blood Watch.
Make sure you still have the quest  The Sun Gate from Vindicator Aesom, then travel to Vindicator's Rest.
Read carefully before you accept the quests. You will be escorted by a level 20 elite shaman NPC. He will deal lots of damage, place totems, and in most cases heal both himself and you if necessary. He might sometimes overpull if he runs into a patrol, so consider pulling for him. He also stops twice to plant explosives. At that time he won't care about adds, so stop pulling!
Fenissa the Assassin, a rare mob, might spawn while doing this quest. You might have already seen her at the Cryo-Core. Ensure you do more than half of the damage to earn her loot! You have to do half of the damage to a mob to earn its loot and be credited the kill, so ensure you damage the mobs the NPC targets, as he will also tank for you most of the time. Also make sure to do enough damage to Sironas to earn credit for her kill.
Accept [20G] Clearing the Way from Vindicator Corin. Talk to Demolitionist Legoso for  Ending Their World. Once you accept this quest, follow Legoso and kill all enemies in your path, including the Sunhawk Agents and Sunhawk Saboteurs. After clearing out the lower area, Legoso asks you to protect him while he sets up the Explosive Charge. After this, continue following Legoso up the hill. After you get to the top, you will see Sironas siphoning the power of the Vector Coil. Kill more of the Sunhawk enemies until he asks you to protect him again as he sets up the second Explosive Charge.
After a few moments, the Charges go off and Sironas increases in size and starts attacking your party. Kill her.
Before leaving the area, be sure you also have all needed kills. After this, you can jump back down the hill on the southern side. Find the Sun Gate. Right click on each of the four Sunhawk Portal Controllers to attack and destroy them. Once they are all gone, you can swim in the water and right click on the Sun Gate itself to attack it until you get a yellow message that you have successfully destroyed it.
Travel back to Vindicator's Rest, turn in [20G] Clearing the Way at Vindicator Corin, then hearth or travel back to Blood Watch.
Prepare for one of your most unique moments in WoW and turn in [20G] Ending Their World at Exarch Admetius. He will then yell out that you are a Hero of the Draenei people. After exiting the building, a procession of NPCs you have been in contact with appears. Enjoy the party on the outside (they all got their special words to tell you, just talk to them). Be certain to talk to Prophet Velen for  The Unwritten Prophecy. Otherwise you'll have to visit him again in The Exodar if you wait too long.