A Nuzlocke is a challenge run of any main series Pokemon game, intended to make the game more difficult. The rules of the challenge are player-defined (and can be customised), though there are some "core" rules which are considered pivotal to the challenge and should not be changed. The rules are enforced by the player, not the game.
The challenge originates from an old webcomic of the same name (language warning). Several variations of the challenge exist, each with different core rules.
Core rules
Death rule: Any Pokemon that faints is considered dead. Traditionally, this means the Pokemon must be released immediately, though it is also acceptable to store them in a PC box permanently.
Encounter rule: The player may only catch the first Pokemon they encounter in each area visited. If the player knocks out their encounter or it flees, then they lose their encounter for that area. Different "areas" are often separated by the name that appears on the game's "save" screen.
Blackout rule: If the player blacks out from a battle (i.e. all the Pokemon in their team die), then they lose the challenge. Alternatively, the player only loses the challenge if all the Pokemon they own are dead.
Trade rule: The player may not use Pokemon traded in from a different game. This includes Mystery Gift Pokemon. (Pokemon caught in the Nuzlocke save file can be traded to allow evolution.)
Reset rule: The player may not reset the game to start again from the last save point (i.e. they may not "try again"). This includes behaviour like soft resetting for a favourable nature, etc.
Common rules
Nickname rule: The player must nickname all their Pokemon.
Set battle rule: The battle style must be on 'Set', and never 'Switch'.
In-battle item rule: The player may not use boosting or healing items from the bag during battle. Alternatively, the player may only use as many healing or boosting items as their opponent does (e.g., the player may use a bag item if Cynthia uses one).
Level rule: The player may not use any Pokemon whose level exceeds the highest level of the upcoming Gym Leader, Elite Four member or Champion. (This blocks grinding as a solution to the challenge.)
Starter rule: The player must choose their starter based upon the last digit of their ID number, e.g. 1-3 means Grass, 4-6 means Fire and 7-9 means Water. If there is a 0, look at the next least significant digit. (This rule is intended to have a similar effect to the 'encounter rule'.)
Pokemon Centre rule: The player may not heal their Pokemon at Pokemon Centres. This means they are dependent on items purchased from shops (making money management a potential factor).
Species rule: If the player's encounter for an area is a Pokemon that is already caught (or part of an evolution family the player already has access to), then the player has the option to catch the next encounter instead.
Bonus feature rule: The player may not use bonus features like Pokemon Amie, Super Training and Pokemon Refresh to make their Pokemon stronger. Some players also ban Exp. Share (where possible) and items like Rare Candies, Exp. Candies, etc.
Shiny rule: Shiny Pokemon are exempt from the encounter rule (and should be treated as a lucky bonus). Outright Shiny hunting is still banned.
Legendary rule: The player may not catch legendary Pokemon. They may also be required to KO any legendary encountered in battle.
Research rule: The player may not research enemy trainers' movesets, etc. or otherwise use the internet to help them beat the challenge.
Notes
The rules of a Nuzlocke are up to the player to decide. If you're not sure whether something breaks a rule, you should simply pick one way or the other and stick with it for the entire run.
The player should decide what happens if any rules are broken during the run. They may lose the challenge or be penalised in some way.
