According to the unit description page, StarCraft's Terran Confederacy discovered an obscure planet called Azeroth, which was home to "a dizzying selection of humans, mutants, and aliens in a state of perpetual superstition and conflict." The Confederacy decided that the Tauren, one of the most physically imposing of Azeroth's species, would make excellent additions to their space marine corps., and equipped the large number of young bulls who were interested in their proposition with state-of-the-art armour and weaponry.
UPDATE: In Starcraft 2, if you head to the north end of the map the "Zero Hour" mission, past the Zerg Base in the northeast section, you will see a Tauren Space Marine near an outhouse. His name is LV80TSM! and upon getting close to him or clicking on him, he rushes into an outhouse. The outhouse cannot be destroyed.
On the Emerald Dream Server (US), there is a RP-PVP-PVE guild called <Tauren Marine>.
The other April Fool's Day pranks from 2008: