What a great idea for a thread! Oh man, this is so difficult considering the amount of hunters I've made and all the pets I've gone through. I'll see what I can remember though. This will be fun to reminisce!
Sorry in advance for the gigantic post I know this will be. >.>
---------------------------------------------------------------------------
My
very first character was a Night Elf called Vephriel. She only got up to about level 30ish before my boyfriend and I switched to Horde.
We only started with Alliance due to our friends being there, but when they stopped playing we were pretty much like 'Screw this, we're heading to the awesome faction'. xD She still exists because I don't have the heart to delete my first character. Anyways, the pets that I remember from her were:
Snapjaw, my first Crocolisk pet. I ran all the way to the Durotar border to get him. Crocs are my favourite animals in real life, so I really wanted one in game. Back then they were so useless as pets, but I had him regardless. Oddly enough I later found out that there were mobs called Snapjaw Crocolisks. I had only chosen the name because it was fitting. xD
Sinthom was her main pet. I wanted a raptor really badly, and since the black ones couldn't be tamed back then, I settled for the dark grey/blue. It was a very exciting moment when I was a high enough level to venture into Wailing Caverns and tame one of those sneaky stealth raptors.

He was the pet that I used to level with.
Charlotte was probably one of the only female pets I've ever owned, but I loved the black widows in game and since I love spiders I had to have one.
Adolf (no, not named after who you're thinking, it just means Wolf) was another pet I remember fondly. My boyfriend and I dared to run into Silverpine together since we really wanted these awesome looking black wolves. We got matching ones. xD
I didn't have all of these at the same time (there weren't that many pet slots back in the day), but I forget who I let go of first and such.
---------------------------------------------------------------------------
The second hunter that I made was a male Tauren named Kastrel. He was also my very first Horde character. I'm not really sure why I chose a male Tauren, but I know I hated the females so I couldn't play one. I think I just liked the race in general.
Anyways, I got him up to around level 35 I believe (I'm a very slow leveller) before Burning Crusade came out and I created Vephriel. After a while she became my favourite and eventually I deleted Kastrel.

His one and only pet was
Humar. Obviously I levelled with something else until 23, but I can't remember what it was nor was it important. As soon as I learned of Humar I had to have him. So at 23 I clearly remembering heading off to the lion tree near Ratchet and camping my butt down for 5 hours straight, unflinchingly waiting for the black lion to spawn. It was the first rare tame I'd ever done, and it was so exciting. I kept the name Humar, since it seemed only fitting, and from that day forwards it was his sole pet.
I actually kept Kastrel around for a long time, even after creating Vephriel, solely because of Humar. Though I knew I wouldn't play that character any more, I felt horrible deleting him because he had a pet that took me so long to get (in my eyes...lol at future Skoll camping and such). At some point I realized that it was pointless, and when I needed the room I let him and Humar go. This is why I feel so glad to have Humar tamed again on my little Troll hunter, Gazini.
---------------------------------------------------------------------------
Then there's Vephriel. Oh boy I've had a lot of pets on Veph. Probably half of which I don't remember. The ones I can though, are the following:
Frankenswine was my buddy. I still regret letting him go sometimes, because I probably had that piggy for 80% of my levels. He started as an armored black boar, but I had the zombie pig in my sights for the future. He was the same pet in my eyes, he only....died or something at some point. xD Anyways, boars were amazing for solo levelling, and before pets had their huge revamp he was the most overpowered thing I've ever tamed. Nothing could take aggro off of him, and his charge was spectacular. It was a sad day when I had to release him for bigger and better pets that came along with BC and WotLK.

Gah, I'm all sad thinking about him now.
Naraku (means Hell in Japanese) was my levelling pet through the 60's. Once I hit Outland I really wanted one of the awesome purple Ravagers with glowy eyes. He was quite a unique pet, and though I didn't like Ravagers at first, they definitely grew on me.
Wraith was my other pet while going through Outland. I really liked the Outland Raptor looks, and his dark grey colouring was to my tastes. Kept him for a long time, though he was eventually overshadowed by the awesomeness of Devilsaurs. :3
Vorpal, yet another pet I had during Outland. I started out with the white skin, but went with the green once I was appropriate level. I loved that they were the closest thing to dragons we could tame. Ideally I was going to tame Gezz since her colouring was absolutely my favourite. I levelled like mad, tried it multiple times and failed, then next thing I knew she couldn't be tamed anymore. ;__; Sad, sad day. I couldn't keep a warp stalker after that, I was too depressed.
Goliath was a short-lived pet, but I loved him while he had his awesome Rhino Bowling. After that was nerfed he just wasn't as fun.
Krauser - I've had this black wolf skin a few times with different names, but eventually I realized I just wasn't as connected to it as I thought. It's still my favourite if I had to choose a wolf model though.
I've had various hunters besides those three, but they were the primary focus. Wow, quite a trip down memory lane. I'm sure no one read all that, but I had fun writing and remembering. ^^