A Murlok atop a Tauren Marine
Murloks are amphibian, humanoid fish-like alien species found on the obscure world of Azeroth. Next to nothing is know about them, except their home world and that they are cooperative with the Tauren, or at least some of them.
Some Taurens are seen with a Murlok, sometimes holding weapons. It is unknow whether Murloks are hired as mercenaries or as mascots.
Note that this information is derived from an April Fool's joke by Blizzard Entertainment and as such, should not be taken as canon.
Trivia
The Murlok are taken directly from the race of Murloc (with a slight change in name) in StarCraft's counterpart universe of Warcraft.
References
StarCraft II: Tauren Marine. Accessed on 2008-01-04