1. Get a pet to 25.
The basic method is to have pets that you battle around the zones, taming good-looking recruits as new pets, and defeating the Tamers in order. As Horde, you should follow Taming Kalimdor to start - then Taming Outland, Taming Northrend, Taming Cataclysm, Taming Pandaria. Each tamer gives you a quest to the next, I think.
Alliance characters do Eastern Kingdoms instead of Kalimdor
which sometimes causes problems for people trying to do pets on characters from both factions. If you have characters on both factions, it’s safest to do either one, but not mix them until you have completed one.
As you do that, you will naturally level your original pets and the ones you tamed along the way.
You will learn about families, and what is strong against what.
There are short-cuts.
If you have a level 100, you can buy your first 25 by getting your Draenor Garrison to Level 3. Then a quest pops up that rewards you an Ultimate Battle-Training Stone, that levels one pet to 25 instantly. However, you will not, of course, learn anything at all from that.
Without that stone, this video shows the fastest method for getting one level 25 pet
Basically, pick up a couple of level 4-6 crabs.
Fly off to Badlands where you can use them to beat level 14 critters.
When you have captured a couple of level 14-16 crabs in Swamp of Sorrows, fly to Valley, where you can beat the Critters and capture a 23.
Now go to the Briny Muck and serve your inevitable hour or two looking for the Blue P/P Emperor Crab you’ll have to catch anyway someday (so you might as well get some XP out of the search).
Once you have one pet at 25, you can buy level-25 pets at the Auction House and learn them.
2. Get a full team of 3 to 25. (Quickly followed by a half-dozen more.)
Beating the high-level tamers requires a decent team. You will need to choose your first pets well, to be able to beat the battles you face. wow-petguide.com has strategies for all major tamers and quests.
Here is a list of the most important pets to get in general - not specifically for Naz and Mech, where most of the load can be carried by a H/H Valk + Ikky or a Sen’jin Fetish + H/P Infected Squirrel - but for use in general:
These are all much-used pets that will serve you well.
You might take special pleasure in doing the Raiding With Leashes achievements to go back and solo old raids, to get the pets that drop from them. You can buy them at the Auction House, but the other way is more fun and more satisfying. 
3. Open up the Pandaria Tamers and the Safari Hat for daily farming.
Pandaria and Draenor Tamers each reward HUGE XP once per day. Once you have defeated all Pandaria Tamers you can challenge them all daily. Draenor Tamers are easier; you can challenge them any time. Amelia is especially easy.
With the right team, you can beat a tamer with two level 25s, and bring in one low-level pet for one round. That low-level pet then scoops the XP jackpot, and gets enormous XP from the tamer battle. A level 1 will get to level 11 in one battle. A level 11 to level 16 in another.
Legion Tamers used in the Family achievement are infinitely repeatable when their eorld quest is up, and are the richest common source of XP.
4. Farm the Legion and Pandaria and Draenor tamers to level more pets.
This guide shows the fastest ways to level once you have some of the most important pets.
This is the stage when you spend your time rehearsing all the battles again and again … and again … and again … 
You will also be collecting more pets from the wild, from old raids, and from the Auction House.
5. Continue with the Pandaria Spirit Tamers.
6. Do the Pet Dungeons and then Celestial Tournament and Family Familiar.
The following addons are near-mandatory:
Rematch (organises pets and saves your teams)
BattlePetBreedID (shows the breed of each pet)
I highly recommend
Pet Tracker
Derangement’s Battle Pet Cooldowns
as well.