The Arcane damage type is the new type of elemental damage introduced in Diablo III. It is characterized by the color purple.
Arcane is a pure magical energy, in forms of astral currents turned to force. Arcane energy rips the reality asunder, distorting space and twisting time itself.
Arcane damage is mostly used by Wizards, who wished to go beyond the simple elemental magic in order to bend the very fabric of reality to their will. The ultimate manifestation of Arcane Power is the Archon. The other classes, for the most part, do not deal Arcane damage: their only source of it would be equipping weapons with bonus Arcane Damage, therefore they will not deal pure Arcane damage, unless they are insanely bold or suicidal enough to simply use a basic attack. Eirena's spells use Arcane damage type as well.
Overall, Arcane is a type of magic related to cosmic matters, runes, starlight, teleportation, time warp and stereotypical fantasy 'power beams'.
Andariel's Visage, Moonlight Ward, Stone of Jordan, Lidless Wall and Gesture of Orpheus are the items with unconventional bonus to Arcane skills damage. Countess Julia's Cameo amulet will render the character completely immune to both Holy and Arcane damage (the attacks will actually heal the Nephalem).
The Arcane damage type was revealed by the Witch Doctor in the Diablo III gameplay video at WWI08. The Witch Doctor was seen wielding a sword imbued with Arcane Damage because of its characteristic purple glow.
After the revealing of the Wizard at Blizzcon, one of whose skill trees includes Arcane Skills, mechanics of Arcane damage were slightly elaborated. Upon inflicting a critical hit, Arcane Spells were to silence opponents, and (with the right synergies) slow them as well. Possibilities of extra damage to spell-casters or doing damage to the opponent's mana pool were discussed as well, much like the Arcane Towers seen in Warcraft III: The Frozen Throne.
It is very possible that Arcane and Holy damage were already present in the first two games, though at the time it would've been known as generalized 'magic damage' as opposed to that of a particular element.
Diablo (Game) examples include:
Zombie (Diablo I) were also immune to magic in the Normal and Hell difficulties, but not Nightmare.
So, the damage type can only be officially be said to have named in Diablo III.
But magic damage was also represented by the color white in many class skills. This leaves the question whether magic damage is distinct from Arcane damage, since it may be possible that the destruction of the Worldstone has caused a new type of energy to flow through Sanctuary.