Since the Cataclysm flooded the graveyard, Don Carlos has moved to the outside of the north wall of Gadgetzan, between the Alliance and Horde mounts tied up there.
The Haliscan Set
It is possible to earn the entire Haliscan set that Don Carlos wears by completing his quest to earn his hat, and by having a tailor craft the rest of the outfit. Additionally, if Don Carlos is defeated on the Heroic setting of Old Hillsbrad, he drops , which allows the wearer to summon a ghost wolf.
Don Carlos' name and appearance may be a reference to Zorro. Zorro also rides a horse, and in The Legend Of Zorro he fights a duel with an old enemy, hence the line "old...friend" that Don Carlos speaks when a player talks to him. (The "old friend" line also explicitly refers to someone revealed over the course of the quest he gives.)
There is also a play by Friedrich Schiller called Don Carlos.
Patch 2.4.3 (2008-07-15): Added.