Many moons ago, I did battery research on Li-ion batteries. The web address provided by spackard actually does a pretty good job of describing what happens when cells are cycled under various conditions, but it's pretty short on details of the underlying chemistry. For anybody interested, I'll give you my best layman's chemistry lesson on Li-ion batteries, at least as I understood matters 10 years ago.
All batteries comprise a cathode and anode. In Li-ion batteries, the cathode is some variant of LiCoO2 (usually doped with some Ni and/or Mn to improve stability), and the anode is typically graphite. Most of the limitations of Li-ion batteries lie in the cathode material.
There are two fundamental issues when a Li-ion battery is charged/discharged: the structural stability of the cathode itself and the electrical conduction between individual grains or crystals) of cathode material.
To understand the issue of structural stability, you first need to know something about LiCoO2. It is a layered compound consisting of alternating layers of lithium, oxygen, and cobalt atoms: Li-O-Co-O-Li-O-... ad infinitum. The layered structure of this compound is critical to its function because during charge/discharge, the Li ions must be mobile, and the layered structure provides a pathway for the Li ions to move into/out of the compound. During charging, the Li ions move out of the structure and migrate toward the anode. During discharge, this process is reversed.
The greater the charging potential, the more Li is removed from the structure, which increases the charge capacity (the amount of energy the battery can store). However, only about 55% of the Li can be removed before the structure becomes unstable (the Co atoms move into the empty sites and cannot move back to their original position). When this happens, the Li migration pathways become blocked, and Li can no longer move into/out of the structure, which means it can no longer function as a battery). The removal of 55% of the lithium corresponds to a charging potential of about 4.3 V. This is why Li-ion batteries should never be charged at higher potentials.
Theoretically, it's impossible to "over-discharge" a Li-ion battery, because after all of the vacant Li sites are again occupied by Li, the chemical reaction ceases. But here's where the other issue arises: as Li transports into/out of the structure of LiCoO2, the LiCoO2 crystals expand and contract (they expand when Li is removed and contract when Li is inserted). This expansion/contraction creates a problem because it causes the individual crystallites to separate and lose electrical conduction.
LiCoO2 is a powder. When prepared as a cathode material, it is ground into a fine powder, mixed with a binder, and coated onto a substrate (usually a conductive plastic film or aluminum foil). But, fundamentally, the prepared cathode consists of small grains of powder that are simply packed closely together. For a battery to function, you need electrons to move freely to/from the cathode/anode, which means that electrons most also move freely between the individual LiCoO2 crystals within the cathode. But when the LiCoO2 crystals expand/contract, small gaps develop between the crystals, and electrical conduction is lost. Any LiCoO2 crystals that lose electrical conduction with the rest of the crystals effectively become "dead."
This loss of conductivity is the reason for limiting the extent of charge/discharge. In effect, you are limiting the expansion/contraction of the LiCoO2 crystals so they don't separate from each other. This expansion/contraction is also responsible for the "coarsening" of the films described in the article linked by spackard. The 80%/20% guideline seems about right to me.
I'll let someone else compact this into a tl;dr version.
