Runestones are small items that can be applied - one each - to any skill, but not to passives or items. Diablo III's skill runes grant special bonuses to the skills with which they are used, altering their effects and generally enhancing them, although the changes that a rune makes to a skill may dramatically alter its utility.
The runes changed drastically after the Beta Patch 13, where players were first able to try them out for themselves.
Runes are a component of the skill system that allows a player to alter a skill, whether that alteration is major or minor. Some runes, such as the Bash rune Unleashed, won't change the basic functionality of the skill, and offer a bonus such as increased resource generation, or increased damage. However, other runes can drastically change the way a skill operates, such as the Witch Doctor's Rain of Toads rune for Plague of Toads, which instead of having a few frogs hop across the ground in an erratic pattern, the frogs then fall from the sky in a directed assault.
The five runes, currently, do not have individual names. This can make communication with other players somewhat confusing. However, each rune's effect on a skill is named. For example changing the Barbarian's skill Cleave into Broad Sweep, Gathering Storm, Scattering Blast, Reaping Swing or Rupture by activating the appropriate rune will apply additional bonuses.
Socketing a rune.
Runes are automatically unlocked upon a pre-determined level. Each skill will list what levels each rune will unlock at, and after the level requirement is met, the skill can then be altered by activating the rune. Runes can be changed at any time, but changing a rune will trigger a 15-second cooldown, during which time the skill or spell will not be available for use.
D3 Runestones vs. D2 Runes
Diablo III's Runes are nothing like the 'runes' found in Diablo II. In D2 there are thirty-three kinds of runes, which are small items that have no use on their own, but can be placed in item sockets to add various bonuses to those items, and in certain combinations produce RuneWords, which add powerful, predetermined sets of bonuses, provided that the item has precisely the right number of sockets.
Diablo III's runes are "socketed" into skills, not items. See the Gems and Sockets articles for more details about item socketing in Diablo III.
Skill Rune Videos
In May 2011 Blizzard released a set of five videos, one for each of the classes, demonstrating various runestones in a single skill each.