How are aircraft depainted?
Paint stripper. Lots of paint stripper. 
(originally I said thinner, but I have been corrected, it's more accurately called stripper)

Seriously though, it's actually not too different to other things that you paint. You need to spray on paint stripper. But, just like when painting the aircraft, it's imperative that you cover up all the delicate systems on the aircraft fuselage.

See here: 
                
            

Also, I think it would be rare to paint a new livery over and existing one without first removing the old paint (maybe only if you were just changing small details), because covering an aircraft in paint weighs A LOT. For a 747 or 777 sized aircraft the paint job can weigh over 1000lbs 

Carrying that around costs fuel and fuel costs a lot!