Previously, only the Mercury's Treads reduced the effect of any kind of CC (by 1 second if my memory is ok).
Now we have 3 items that allow you to reduce any kind of CC: Mercury's Treads, Moonflair Spellblade and Cloak and Dagger. All of these items gives you +35 Tenacity.
How does Tenacity work? Is it a kind of percent reduction based on the duration of the CC or it is a specific amount of static time for all the CCs?
Tenacity is a mechanic that reduces the duration of crowd control effects. It does not affect the potency/strength of the effect.
Tenacity works on: Blind, Forced Actions (Charm, Fear and Taunt), Pacify, Silence, Snare, Slow and Stun.
Tenacity does not work on: Airborne (Knockback, Knockup and Pull) and Suppression.
Contrary to Deotronic's answer, Tenacity does not reduce the amount of slow. It only reduces the duration of the any of the CC that is affected by Tenacity. The reduction is reduced by a percentage equal to the Tenacity value. So a champion with 35 Tenacity will have all affected CC reduced by 35% duration.
EDITED to reflect changes to Season 3 tenacity items:
Please note that Tenacity does not stack. There are currently 3 items which provide Tenacity, and they all give 35 Tenacity. If you buy two of these items, you will not get 70 tenacity. You will only benefit from 35.
They don't stack, you can only get the effect from one of the tenacity items. Each point of tenacity reduces the CC by 1%, so any of the tenacity items will reduce it by a total of 35%.
Tenacity is covered fairly well on its Wikia entry.
However, in general you're correct: It's a percentage reduction of many, but not all, CC effects. The percentage reduction is the same as the value of the stat; i.e., 35 Tenacity means a 35% reduction of CC effects.
It does not work on Displacement Effects (knockups, knockbacks, and pulls) or on suppression. As Jay points out, it also does not impact the magnitude of a slow, but only the duration of the slow.
You cannot stack Tenacity items, so at this point, you can only get 35 Tenacity (as all items give the same amount). However, Tenacity does stack multiplicatively with other forms of CC reduction. For example, at max level Trundle's Contaminate gives him 40% CC reduction. If you have 35 Tenacity, your final CC reduction is 54% (35% of 40 is 14, 40 + 14 = 54).
