For the first 70 points, you can go to any starter zone, there is not much difference between them. You can also just skip to the next part in the guide if you have a higher level character.
You will gather the following herbs: [Peacebloom], [Silverleaf], [Earthroot]
Tirisfal GladesElwynn Forest

70 - 125 HerbalismYou will gather the following herbs: [Mageroyal], [Briarthorn], [Bruiseweed]
Learn Herbalism Journeyman then head to Hillsbrad Foothills. It's a horde only zone, this means it might be a bit harder to reach it for alliance players, and for low level players I recommend Darkshore.
Hillsbrad FoothillsThere is just so much herb in this zone. You can find Frozen Herbs at the top of Alterac Mountains, and they can contain Mageroyal, Briarthorn or Bruiseweed.
Darkshore

125 - 200 HerbalismVisit your trainer and learn Herbalism Expert.
You will gather the following herbs: [Kingsblood], [Fadeleaf], [Khadgar's Whisker], [Goldthorn]
There is no Goldthorn at Western Plaguelands, go to Feralas if you want to farm it.
FeralasWestern Plaguelands

200 - 275 HerbalismIMPORTANT! Don't forget to visit your trainer and learn Herbalism Artisan!
You will gather the following herb: [Sungrass]
You will need herbalism 230 to get full Sungrasses, so between 200-230 you will only get Sungrass Stalk.
In both of the zones below the most common herb will be [Sungrass]. I recommend Thousand Needles, because in Eastern Plaguelands, there are a lot of [Khadgar's Whisker] which will be green to you and grey for the last few points. I also like the easy layout of Thousand Needles, you just go in a straight line and you can't miss the herbs.
Thousand NeedlesIf you don't have a flying mount, then when you reach the end of the yellow line, you should turn back and run back to the starting point of the yellow line. You will also have to swim to Twilight Bulwark or Twilight Withering, else you can't really get to the place where the herbs are. (you can see these zones if you click on the map below)
Eastern Plaguelands

275 - 325 HerbalismVisit your trainer and learn Herbalism Master.
You will gather the following herbs:
Swamp of Sorrows: [Golden Sansam], [Sorrowmoss]
Felwood: [Gromsblood], [Purple Lotus], [Dreamfoil], [Golden Sansam]
Swamp of SorrowsThe whole zone is filled with herbs. You can find them everywhere, there is no farming route for this map. If you don't need the herbs for herbalism, you can also stay in Swamp of Sorrows until you reach 350 and skip Outland. But if you go to Outland you will get more expensive herbs.
Felwood


325 - 350 HerbalismYou will gather the following herbs: [Felweed], [Dreaming Glory], [Terocone]
The orange circles means that you should fly around that zone because the herbs are spread all over inside them.
Terrokar Forest

350 - 400 HerbalismLearn Herbalism Grand Master. In Howling Fjord, you will mostly find [Goldclover], but there will be some [Tiger Lily] near the rivers and lakes.
Howling Fjord

400 - 425 HerbalismSholazar Basin is filled with Herbs. The most common herb is [Adder's Tongue], but you can also find some [Goldclover] and [Tiger Lily]. If you don't really care about selling the Herbs, you should stay in Sholazar Basin until you reach 450. All it takes is just one full circuit in the zone, assuming no one else is farming there.
Sholazar Basin

425 - 475 HerbalismVisit your trainer and learn Herbalism Illustrious.
You will gather [Cinderbloom] at Mount Hyjal
Mount Hyjal


475 - 500 HerbalismGo to Deepholm and gather [Heartblossom].
Deepholm

500 - 545You will gather [Green Tea Leaf] and [Rain Poppy].
Visit your trainer and learn the next rank of Herbalism.
Jade ForestI have two routes that I usually use, depending on how many players are farming in the zone. If you are the only one in the zone, then I recommend using the first route.

545 - 575You will gather [Silkweed]. Just follow the route below and gather every herb until you reach 575.
Valley of the Four Winds
575 - 600You will gather [Snow Lily]. There are a few caves in the mountains, but I only recommend to go into the caves if you have some kind of sprint/stealth ability, or if someone else is farming in the zone.
Kun-Lai Summit

600 - 700You can learn the new rank of herbalism from [A Compendium of the Herbs of Draenor]. You can get this scroll by picking herbs at Draenor.

Frostfire Ridge
Shadowmoon Valley
>
700 - 800You get the next rank of Herbalism by simply picking a herb in any of the new Legion zones at the Broken Isle.
For the last few points, every herb will be grey, so your only option is to do the Herbalism World quest because gathering [Felwort] will still give skill points. The [Felwort] quest will only show up every 2-3 days.
Unlocking World QuestsComplete Uniting the Isles by reaching friendly reputation with every Legion faction. You can get this quest from Archmage Khadgar.
After you unlocked the quests, you have to level your Herbalism to at least 100 to unlock the profession World quests.
Darkmoon FaireYou should check your Calendar in-game to see if the Darkmoon Faire is open, the event starts at 00:01 on the Sunday before the 1st Monday of each month.
You can gain +5 skill points by completing a single quest (use it at 795). Click here to read more about the quests.

Val'sharahBelow is a farming route for Dreamleaf which I think is one of the better zones for leveling herbalism, but you can level in any other zone.
Rest of the farming routes:  Aethril farming,  Foxflower farming,  Fjarnskaggl farming,  Starlight Rose farming