The "legend rule" is the name for a rule that prevents a single player from having two or more of the same legendary permanent in play at the same time. If the same player controls two or more legendary permanents of the same name, that player will choose one of those permanents, and the others are sent 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, depending on how they are controlled), and Mirror Gallery cancels out this rule.
"Legend Rule" Change in Magic 2014
This rule was updated under the new rules of Magic 2014. The rule used to affect the entire battlefield (regardless of the legendary permanents' controllers) and would send all of those legendary permanents to their owners' graveyards.
One way to think about the new "legend rule" is that it 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.