Start by paying attention to the elemental strengths and weaknesses. For example, that link Linaomine posted is a good idea. However, it was GREAT for leveling up my Nordrassil Wisp, Jade Oozeling, and Oily Slimeling. Magic is strong against Flying. They breezed through the Dragonbone Hatchlings. And, you would probably want to raise a Flying pet now that you probably caught one. Flying is strong against Aquatic. So, look for crabs and frogs which are usually by the shoreline.
That will also help you pick up pets that may seem tough. Fel Flame in Shadowmoon Valley hits like a tank. But, Critters, although strong against Undead, have a defensive strength against elemental damage. Even if you didn't have a sufficient Aquatic pet, you can still mash it out with a Critter, like a roach of some sort.
Just to recap, it's all about those strengths and weaknesses. If you don't have a pet that's strong, you may have one that the other pet is weak against. If you do have one that's strong, you can fight pets 2-3 levels higher.
Something else that I do, because I have 4 level 25 pets now, I'll let the 25 do all the dirty work until the final pet has very little HP. I keep passing until the first pet dies. Then, switch in the other pet to finish it up to get the super bonus. The original pet is dead and doesn't get any XP anyway. Perhaps, that's a glitch. Usually, in the game, when you die, you still pick up XP. But, when the pet dies, it gets nothing if you win the match. The last pet standing gets all the credit although it did very little work. The only problem is, will the pet survive - not miss 4x in a row or get one-shotted.
My only problem is leveling up Elementals. I have a Fel Flame and Water Waveling, both at level 20 now. They're strong against Mechanical pet. The highest mechanical pets are 17 in Winterspring and you rarely see them. Also, not a lot of Undead around for Critter leveling, only 17 in Kara.