The "legend rule" is the name for a rule that prevents two or more of the same legendary permanent from being in play at the same time. If a legendary permanent is in play, and one or more legendary permanents of the same name is put into play, all will go to their owners' graveyards when state-based effects are checked. This is not a destruction effect, and can't be prevented by regeneration or indestructibility.
At this time, only two cards circumvent the "legend rule." Brothers Yamazaki allows up to two of them to be in play at the same time (though a third will send at least one to the graveyard, depends on how they are controlled), and Mirror Gallery cancels out this rule.
Magic 2014 change
Under the new rules of Magic 2014, any time two or more legendary permanents with the same name are controlled by a player, that player chooses one of them and the rest are put into their owners' graveyards as a state-based action. 
One way to think about it is the "legend rule" now looks at each player individually. It doesn't matter what any other player controls. Clearly, this has a few play ramifications. If you control a legendary permanent, having another one enter the battlefield (by playing a second one or creating a copy of the first one) will leave you with one on the battlefield. It may be the old one. It may be the new one. That's up to you.
Also, creating a copy of a legendary permanent controlled by another player will simply give you a copy. The one controlled by the other player won't explode, won't leave the battlefield, and really won't be affected at all. Clones do what they were intended to do, which isn't to be situational killing machines.
- If an effect asks a player to choose a creature type, Legend is not a valid option.
- Changing a legendary creature's type or subtypes doesn't stop it from being legendary.