Fear is an Evasion Ability present mostly on black creatures. Creatures with fear can only be blocked by black and/or artifact creatures. The most likely reasoning behind this is that the creature is so fearsome, so utterly gruesome and repulsive, that only other repulsive things (black) would dare to come near it. As for the artifact creatures, it's because they don't usually have any mind and thus do not fear anything. As of the release of Zendikar, Fear has been replaced with Intimidate.
The mechanic has always been in Magic, but it was not always called Fear. In fact, the base set included a card called Fear, an aura that gave Fear to the enchanted creature. The mechanic was printed in its entirety on creatures for a long time, until it was finally keyworded in 8th Edition.
Fear appears mostly on black creatures, as black certainly has a monopoly on fear. However, it has appeared in other sources. Two artifact creatures with Fear automatically given to them (though some others can gain it through special conditions) are Dross Golem and Arcboud Fiend. Fear also appeared in similar ways with a change of color on white and red cards even as far back as Legends. Seeker was made to be a white version of Fear, and in Planar Chaos, "firefear" was given to red cards such as Firefright Mage. Also in Planar Chaos a white creature, Dust Elemental, was given fear. These have only been minor splashes, though, and black maintains an overwhelming majority of Fear cards.