(sorry about being long ... and some folks might add/subtract some)
With the recent changes, being "efficient" merely means that you have to have a better idea which pets you need, and must have. For example, Anubiseth is used in many fights, and is an important player, as well as a strong arsenal of Whelplings, so make sure that you go farm out Dustwallow, for one, and include the Spawn of Onyxia (hard to get a Blue in any of these ... so be ready to use a rock!) and then march over to Feralas and farm another one. I imagine those are the easiest to do, even though they are a bit time consuming. The Spawn of Onyxia is a fight, so be ready for it.
The thing that has become the most important for me, is making sure that you do the daily at the Menagerie, and then go do the set of 6 dailies on the 6 trainers in Gorgrond, Nagrand, Talador, Frostfire, Shadowmoon and the Spires of Arak. That's 12 Charms right there, and plus the daily Menagerie that's 16 to 17 of them, and that allows for a Blue Rock daily to get the right pets upgraded, IF they are the right ones, which is another story. Don't (DO NOT) try some of these dailies if you do not have some of the basic required pets. And make sure that you get the Darkmoon Tonk and Zeppelin for sure.
Many of the strategies list the pet type ... B/B, or S/S, or P/P and many other variations. In general, some pets, you want the SPEED, and that means S/S is huge, specially in Whelplings. But others need the power and others need something else. Generally, if you have 2 of them, at least make sure they DIFFER in their stats so you can see the difference. The pet with the highest speed number, usually goes first, and you might be able to cancel out some punishment by being prepared.
One last bit, from me, and I am not the expert in this, is Pet Tracker. Aside from helping you chase pets in every zone, to get the Accomplishment, it also shows you the spells the pets are using against you, and that is handy, so you can tell you can do something else one more round, and then Burrow/Dive, so the big hit does not come, for example. In some ways, you want to learn to "mitigate" the damage, that is cut it down as much as possible, with the right counter pet, or at least the right ability at the right time.
This, of course, makes Pet Battles a bit more studious and interesting, than the regular game for me, which is the same all the time. Here, there are endless combinations and if you use the abilities correctly, you will be just fine.
One last bit ... beware your early days of using your preferred pet, and you end up getting beat up badly after a while, and possibly frustrated. In the meantime, try to get an Unborn Val'kyr, if you have the time, and check the area under Dalaran for the three spots marked on the Pet Tracker, and just be ready to fight a little Undead. She's cool and probably the best looking Pet of all of them! BUT, do not get discouraged by strategies that use her. There are many replacement Undead Pets that you can use in her place if you have to, or need to. Might not make as much damage, but the difference might be smaller than we think since most strategies listed with her are a waste of the rest of her abilities!