How are the categories for climbs decided?
As noted above, part of the ranking of a climb depends on its placement within a stage: usually, the ending climb of a stage gets "bumped up" by a category. You can see that in the plots below, which show climbs as categorized by the organizers of the Tour de France itself for the 2012, 2007, 2005, and 2004 editions of the Tour, and plotted by the length of the climb and its average gradient. If given the length of the climb and gradient, you can calculate the total elevation change for that climb, and the dotted contour lines in each plot show that. Cat 2, 1, and HC climbs are named. For example, in 2004 the Vilard de Lans climb was classified at a Cat 2 climb rather than (evidently) a Cat 3 because it was the end of the stage. Similarly, in 2005 the climb to Pla d'Adet ended the stage, and it appears that its category was also increased from (arguably) Cat 1 to HC. 

As an aside, the Madeleine was climbed in both 2004 and 2005 but, as you can see, the length and gradient of the climbs were different in those years. In 2004, the Madeleine was climbed from the southern side; in 2005 and 2012, the approach to the Madeleine was from the north.