A mnemonic phrase, mnemonic recovery phrase or mnemonic seed is a list of words which store all the information needed to recover a Bitcoin wallet. Wallet software will typically generate a mnemonic backup phrase and instruct the user to write it down on paper. If the user's computer breaks or their hard drive becomes corrupted, they can download the same wallet software again and use the paper backup to get their bitcoins back.
Anybody else who discovers the phrase can steal the bitcoins, so it must be kept safe like jewels or cash. For example, it must not be typed into any website.
An example of a mnemonic phrase is:
witch collapse practice feed shame open despair creek road again ice least
The word order is important.
A simplified explanation of how mnemonic phrases work is that the wallet software has a wordlist taken from a dictionary, with each word assigned to a number. The mnemonic phrase can be converted to a number which is used as the seed to a deterministic wallet that generates all the key pairs used in the wallet.
The English-language wordlist for the BIP39 standard has 2048 words, so if the phrase contained only 12 random words, the number of possible combinations would be 2048^12 = 2^132 and the phrase would have 132 bits of security. However, some of the data in a BIP39 phrase is not random, so the actual security of a 12-word BIP39 mnemonic phrase is only 128 bits. This is approximately the same strength as all Bitcoin private keys, so most experts consider it to be sufficiently secure.
It is not safe to invent your own mnemonic phrase because humans are bad at generating randomness. The best way is to allow the wallet software to generate the phrase which you write down.
Two-Factor Mnemonic Phrases
Mnemonic phrases, like all backups, can store any amount of bitcoins. It's a weird idea to possibly have enough money to purchase the entire building just sitting on a sheet of paper without any protection. For this reason many wallets make it possible to encrypt a mnemonic phrase with a password.
The password can be used to create a two-factor mnemonic phrase where both "something you have" plus "something you know" is required to unlock the bitcoins.
This works by the wallet creating a mnemonic phrase and asking the user for a password. Then both the mnemonic phrase and extra word are required to recover the wallet. Electrum and some other wallets call the passphrase a "seed extension", "mnemonic extension" or "13th/25th word". The BIP39 standard defines a way of passphrase-protecting a mnemonic seed. A similar scheme is also used in the Electrum standard. If a passphrase is not present, an empty string "" is used instead.
Warning: Forgetting this password will result in the bitcoin wallet and any contained money being lost. Do not overestimate your ability to remember passphrases especially when you may not use it very often.
Warning: The mnemonic phrase password should not be confused with the password used to encrypt the wallet file on disk. This is probably why many wallets call it an extension word instead of a password.
This feature also provides plausible deniability, because every password generates a valid seed (and thus a deterministic wallet) but only the correct one will make the desired wallet available. You could create a decoy wallet which has the same mnemonic phrase but a different password, and if physically coerced then reveal only the first password and keep the second a secret.
On the other hand, the entity coercing you may already know about the concept of decoy wallets. They could continue beating you until you give up two or three passphrases.
For a longer discussion of this problem see Storing bitcoins#The 5 dollar wrench attack
Storing Mnemonic Phrases for the Long Term
Most people write down phrases on paper but they can be stored in many other ways such as memorizing, engraving on metal, writing in the margins of a book, chiseling into a stone tablet or any other creative and inventive way.
Some people get the idea to split up their phrases. Storing 6 words in one location and the other 6 words in another location. This is a bad idea and should not be done, because if one set of 6 words is discovered then it becomes easier to bruteforce the rest of the phrase. Storing bitcoins in multiple locations like this should be done via multisignature wallets instead.
Another bad idea is to add random decoy words that are somehow meaningful to you, and later remove them to be left only with the 12 word phrase. The phrase words come from a known dictionary (see next section), so anybody can use that dictionary to weed out the decoy words.
Generally a mnemonic phrase only works with the same wallet software that created it. If storing for a long period of time it's a good idea to write the name of the wallet too.
The BIP39 English word list has each word being uniquely identified by the first four letters, which can be useful when space to write them is scarce.