Until you get to level 48, the only Owls available are the ones in the elven starting area. Getting one of those with a Horde character is doable, but will take several hours and a LOT of deaths. In theory, you can get one at level 10, but the higher you get, the easier it will be to get there. In other words, you can make up for the longer pet leveling time by getting there faster if you are a higher level. Mid teens is probably the ideal level to go.
Before starting, either put your equipment in the bank or make sure you have sufficient inventory space to put everything you have equipped into your inventory. This will save the loss of durability to your items that will happen from the multiple deaths and the spirit resurrection at the end. You might also want to bring a stack of low-end meat to feed your Owl as soon as he is tamed.
Start from Crossroads and follow the road north. Once you cross into the Ashenvale zone, you should turn on Beast tracking. As you start heading north, keep an eye to both your left for Elementals and your right for Slimes. They don’t usually wander to the road, but they might get close enough to aggro you. Continue north on the road until it forks, then turn left. You will continue on this road about halfway across the zone. There are level 21+ bears that wander onto the road occasionally, so keep your eyes open. Once you approach the city of Astranaar look for a valley that dips down to your right. There will usually be a couple of 20+ spiders here that you need to get past. You are going to follow this around the lake (watch for the bear that sometimes hangs out mid-way around). Once you are around the lake, you’ll meet up with the main road again — follow that all the way into the Darkshore zone. Follow the road about halfway up the Darkshore zone until you see the town of Auberdine on your left.
Your goal in Auberdine is to get on the boat to Darnasus. There are two boats here — the one you want is on the right side as you face Auberdine from the main road you came in on. You will be killed frequently here — the goal is to resurrect yourself closer and closer to the boat until finally you can resurrect yourself on the boat. You can avoid a couple of deaths by going down to the water on the left, and swimming around to the other side of the building the dock connects to. Run up into the building and head for the docks. You’ll probably be killed before you reach the docks, and will appear at a graveyard a ways north of Auberdine. Run down in spirit form, rez as far away from your body and as close to the boat as you can make it and immediately start running. Once you get to where you die near the boat, you can come back in spirit form, wait for the boat to show up, cross into the boat in spirit form and go downstairs to resurrect. (Note: an alternate strategy is to swim under one of the boats, deliberatey have a sea monster kill you underneath, then return to the boat hold in ghost form before rezzing) Give yourself 30-60 seconds, then ease up top to see if you are moving. If you are moving, you are safe. Note that this boat does not cross any zones, so you won’t switch to an overview map. It’s important that you get up to the left side of the boat and watch for the landing dock. You need to jump into the water and swim to shore just before the boat reaches the dock.
You are now in a village outside of Darnasus. You need to skirt to the left of the building you see. Once behind the building you will see a pink glowing portal with two guards. Your goal is to make it through that pink portal. You can try using a disposable pet to distract the guards, but they will kill it in one or two hits. Chances are you will be killed just shy of the portal and will find yourself all the way back at the graveyard north of Auberdine. Not a problem — just run back to the docks in spirit form and take the boat across. This time you can wait for the boat to dock. Get as close to the portal as you can, rez and instantly run for the portal. You will either die going through, or immediately on the other side in the capital. If you make it through the portal before dying, then when you release your spirit, you will appear at a graveyard at Dolanaar.
Instead of running back, you are going to have the Spirit Healer rez you. Before you do, look around to spot where the guards are — because they may aggro you the moment the spirit rez’s you. Rez and run away from the guards. If you get away, then you are home free. It’s a good idea to check your PvP flag at this point — while most of the alliance around will be lower then you, you will have rez sickness and be without armor, so they could easily kill you. If you are flagged, find a bush to hide behind, and wait out your flag timer. Now look for the road heading west towards Darnasus. Follow that road until it crosses a bridge. On your left will be level 7-8 Owls which you can tame that will not come with Claw. If you go past the hut on your right and follow that road, you will find 9-10 Owls that do come with Claw. Tame whichever you want and hearthstone out with your new pet.