1. Unlocking pet battles
To take your first steps into the world of pet battling you first have to learn the Pet Battle skill on your account. You can do this easily at Audrey Burnhep
in Stormwind or at Varzok
in Orgrimmar. You should also do the first quests in the quest chain to enable and learn the basics - tracking, healing, capturing.
2. The first level 25 battle pet
Despite the fact that many of the newer fights and encounters are scaling (meaning that the level of the enemy pets adapts to the levels of the pets you are using and therefore can be done with level 1 pets) most older fights as well as specific achievements, dungeons and quest chains (e.g. the Falcosaurs) don't scale.
Furthermore pet battles, whether PvE or PvP, are most exciting and entertaining in the level 25 bracket.
Having a level 25 pet brings many advantages. You can learn new pets of this level at any time (like from the auction house) and you can also catch high level pets in addition to very quickly leveling weaker pets as your stronger ones can carry them.
There are various ways to get your first pet to level 25. Each has its pros and cons, and which you choose is a matter of taste.
Here are the methods:
2.1 The classic way
The classic way might be slowest, but it gently introduces you to pet battles and teaches you many basics you'll need later.
The journey begins at the trainers who unlocked pet battles for you (Audrey Burnhep in Stormwind or Varzok in Orgrimmar).
Once you have learned the Pet Battle talent, they will give you a quest chain which leads you to multiple trainers to beat them one after another.
Catching and fighting some of the wild pets on your way will strengthen your team so it can withstand the increasingly powerful opponents in the high level areas and finally reach level 25.
At the end of the quest and achievement chain in Pandaria you obtain the Safari Hat which you can use at any time to increase the pet battle experience you gain by 10%.
Even though you may choose the pets you like on this journey, there are some that bring specific advantages.
Some suggestions for good beginner pets:
Many of the pets you encounter in the wilderness and those of the first trainers are Critters or Beasts. If you use pets with Beast attacks - strong against Critters - or Mechanical attacks - strong against Beasts - you will have an advantage.
Your pets of choice should have the highest quality (rare or blue), since those are stronger. You can upgrade pets of lesser than rare quality with Battle-Stones but you probably won't have those at the beginning.
Of course it will also come in handy when your first pets are some that are useful later on.
Have a look at the Most Used Pets.
It is possible to speed the classic method up a bit by catching particularly strong pets and thus "skip" some levels.
Here is a video that shows how this shortcut can look:
However in doing so you miss the purpose of the classic method that is the cautious approach and familiarising with the mechanics. You will also skip quests for the Taming the World achievement.
If those points aren't that important to you then there are much faster methods you could use:
2.2 The easy way
The easiest method, which doesn't require you to do a single pet battle, starts in the Garrison from WoD.
The objective is to do a short quest that rewards you with an Ultimate Battle-Training Stone. This can instantly level up a pet to 25.
All you need is a Garrison on level 3. Don't worry if you don't have one on your characters; catching up on that doesn't take long.
However, something that can take some time is obtaining the 2000 Garrison resources (and 5000g) to upgrade to the 3rd level of the Garrison.
To get these you could either do quests, kill rare mobs, and find treasures (very tedious), wait ~two weeks to get them automatically from your Garrison's cache (very time-consuming), or you could buy Huge Ogre Caches from the auction house. The last will take only a few minutes, but cost you some gold.
Once your Garrison is upgraded you have to go to the site of the Menagerie, get the quest Unearthed Magic from either Lio the Lioness (alliance) or Serr'ah (horde), get the stone from the mine, and turn the quest back in. You'll be rewarded with the Ultimate Battle-Training Stone.
By the way, you can do this once with each of your characters!
2.3 The new way
The new method can also be very quick, under the right circumstances even quicker than using the Garrison.
Since the new (BfA) pet battles are scaling you can get the Polished Pet Charms with level 1 pets. This currency can be exchanged for an Ultimate Battle-Training Stone.
Quite often there are enough pet battle world quests active to get the 60 Charms you need for the stone. Even if not, you can repeat the quests on other characters since the Charms are bound to the account.
However doing this method requires you to do some pet battles (~3-6) that aren't always easy, even when reduced to Level 1 fights.
You should look at the types of the enemy pets and pick your counters accordingly (e.g. an elemental pet vs. a mechanical one).
You can also get Polished Pet Charms for some missions from the mission command table.
Once you have obtained 60 charms the stone can be bought from one of those traders:
Dana Pull in Boralus (alliance)
Koari in Dazar'alor (horde)
Serr'ah in Dalaran (horde)
Serr'ah in Frostwall (horde garrison)
Lio the Lioness in Lunarfall (alliance garrison)
Lio the Lioness in Dalaran (alliance)
Zununu the Undefeated in Dazar'alor
3. And after that...?
Once you have your first level 25 pet you can learn and catch new pets of every level at any time.
Often you can find very cheap high level pets in the auction house to quickly expand your collection.
If you want to level more pets quickly, you shouId get some of the pets that are required for powerleveling: Guide: Powerleveling.
You could for example aim towards getting a leveling team that can fast and reliably beat Squirt.
If you have a certain goal (e.g. a dungeon) you can use the ready-checker of the respective page to check which pets you still need and have to level up.