Runestones is the old name for Skill Runes, which provide five different functions for every skill in Diablo III. All rune forms offer some sort of upgrade over the original skill, and there are virtually no scenarios when a character is better off using the base skill than one of the rune effects.
The five Runes.
The rune effects become available gradually, as a character levels up. All of the basic skills are available by level 30, but a character must reach level 60 to gain access to all of the rune effects, with at least 1, and usually 2 or 3 added each level up from 6 to 60. There is no set pattern or regular system to when the rune effects become available. Characters do not get another rune effect in a skill every 6 or 8 levels, for instance.
The name "runes" is something of a remnant, as there's no real reason the final game system should use that term at all, since the different "runes" are simply graphical icons attached to each of the five different forms of each skill. Originally, the skill runes were called "runestones" which were small items that characters found and socketed into their skills to grant the bonus effects. The item style of runes evolved repeatedly during development, and was eventually removed in early 2012, when skill runes lost their random effects and rune levels, and were integrated completely into the skill interface.
Rune Archive -- Runes evolved greatly during the development of Diablo III. See the archive page for a detailed history lesson.
Players once assumed that a sixth rune would be added in the Diablo III expansion, but with the final game system this seems unlikely, as all the rune effects are now customized to each skill, rather than each runestome type adding a semi-predictable effect to any skill it was added to.
The final game rune system was introduced in early 2012 in Beta Patch 13, where players were first able to try them out for themselves. Runes are now effects in skills, can be switched between freely, and are entirely divorced in organization from the old runestone items system.
Socketing a rune.
Runes are now a component of the skill system that allows a player to alter a skill. Some runes, such as the Bash rune Unleashed, do not change the basic functionality of the skill, simply increasing the damage or duration, or lowering the resource cost. Other rune effects do much more, entirely changing the function of skills from offensive to defensive, or changing the function greatly, such as the Witch Doctor's Rain of Toads rune for Plague of Toads. That rune takes a short range, slow, erratically-moving projectile attack and changes it to a ranged attack with almost full screen range that deals heavy damage to a targeted location.
Runes are automatically unlocked at predetermined levels. Each skill lists what levels each rune unlocks at, and players receive notification of the new runes that have become available each time they level up. Runes can be changed at any time, but changing a skill or rune while not in town will trigger a 10-second cooldown, during which time the skill or spell will not be available for use or further modification.
In May 2011 Blizzard released a set of five videos, one for each of the classes, demonstrating various runestones in a single skill each. These show early versions of teh rune effects, and do not correspond exactly to what we see in the final game.
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.