I chose two:
My hunter just sorta stubles upon them and they become her/his companion and
Other. I use a combination of both. For Rhyela, she uses a "mind-link", or a telepathic communication with whichever beast she is wanting to tame. For some beasts, she has to convince them to join. Others she simply tells her story and they agree to travel with her for their own reasons. But in one way or another, the creatures come to see her as a friend, and of course Rhyela feels the same way about them.
Rhyela's first endeavors as a hunter brought her to The Barrens in Kalimdor. She was awed by the sheer size of the place, and how vastly different the landscape was in comparison to her home in Teldrassil. She immediately fell in love with the lions she saw, but there wasn't any particular one she felt an attraction to. But then, her huntress companion Verdantia told her of a mythical white lion by the name of Echeyakee who would only come to the calling of a special horn. She knew his location when she saw it - a large pile of bones with many lions in the vicinity. And so, Rhyela waited at that spot, waiting for the chance to meet this lion. Finally, a Forsaken arrived. Rhyela was very wary and ready to defend herself if he made any move against her, but he didn't. As she watched, the Forsaken retrieved a horn, and as it sounded through The Barrens, she was stricken with awe at the lion who approached - it was Echeyakee, without a doubt. The Forsaken nodded at Rhyela, and Rhyela took the opportunity to contact Echeyakee's mind to plead with him to join her. After hearing her story of how she was a fresh huntress just beginning her travels, and had been looking for a friend, he was moved to aid her and become the lifelong friend she sought. She thanked the Forsaken, and with her new friend Tetsusaiga at her side, they began a lifelong journey together.
For a creature like Apollyon (King Krush), who I envision as very confident and perhaps even arrogant, it was a very tough challenge. But finally, after struggling with his amazingly powerful mind and will, he realized
her power and what she had to offer, and agreed to aid her. I want to make it clear that she didn't force him to go with her, but she had to prove to him that she was worthy in his eyes as a master, or better yet, friend. After all, he is the strongest beast in Sholazar, and only the strongest partner will do for him.

After fighting alongside her in many battles, he can see that she fights with the ferocity of a devilsaur, and he holds the utmost respect for her.
Then, there's Sheldon. He's an easy-going, light-hearted turtle. All it took to win him over was some gentle pats on the head and some fishies. He's more like a loyal old dog than anything, and loves Rhyela to death. He's taking a break right now at Rhyela's request, but they agreed to meet again soon. Sheldon, loyal as he is, will be waiting for Rhyela when she comes back. She might have to bring a fish, though.
Dante (Loque'nahak) was tolerant of Rhyela's presence when they first met. But he, like King Krush, was very powerful, and when she attempted to contact his consciousness with her mind, he was offended and tried to attack her. But, he was a bit wiser and less haughty than King Krush, so he perceived her good intentions and agreed to lend his power to her, and travel at her side.
With Shikon, she was a gentle soul wandering Zul'Drak without a purpose because of memory loss upon the death of her living body. When Rhyela found her one day, she could sense Rhyela's fondness for creatures, and was drawn to her. Rhyela didn't think twice about welcoming the gentle, ethereal tiger into her heart. Shikon hopes to one day remember what brought her to Zul'Drak, but in the meantime, she is just overjoyed that she doesn't have to be alone anymore.
Rainey had an adventurer's heart and was bored with Darkshore. When Rhyela showed up, it was a golden opportunity to finally go out and see the world. Rainey had felt obligated to remain in Darkshore due to her two young fledgelings, but Rhyela convinced her that they were old enough to fend for themselves, so Rainey joined. Rainey loves traveling with Rhyela because she gets to travel all over Azeroth. She's spunky and rambunctious, but loving and kind, almost like Rhyela herself but in a tallstrider body.
/cheese
