Is the old paint removed before applying a new one?
Yes, paint imposes a significant weight penalty on larger aircraft. On commercial airliners, that weight translates to a reduction in cargo, passenger and fuel carrying capacity, and that means less money to be made on every flight. That is why some airlines have chosen to remove most of the paint and opt for the bare-metal look. However, there are tradeoffs to be considered, such as the fact that bare metal is much more susceptible to corrosion. 

These days removing paint from an aircraft is a relatively straightforward proposition if you know what you are doing. There are a number of environmentally-friendly paint stripping chemicals available that when applied to the aircraft surface, cause the paint to bubble and lift off the underlying airframe.

The paint can then be scraped off with plastic tools or removed with a pressure washer, and the stripping chemical is washed off. Other products are then used to clean remaining residue, treat the metal for corrosion protection, prime and paint.

This explanation is intentionally simplistic, but it covers the basics to answer your question. If you want to see the process in action, you might check the many YouTube videos that show time-lapse recordings of aircraft being painted. Personally. I think they are fun to watch. :)