How are newly discovered objects (stars, planets, galaxies...) named? When a new astronomical object (star, planet, galaxy, comet, etc.) is discovered, what is the official procedure to name it? Who decides about the name of it? Can they be changed in time?
Extra question: How were the areas on the surface of the Moon and planet Mars named?
 A: When new solar system objects are discovered, the discoverer has the right to select the name.  It is submitted to the International Astronomical Union (IAU) for approval but very rarely do they get denied.  We almost had a Kuiper Belt Object named after our oldest daugher when my wife (as a postdoc) and her advisor discovered a large number of binary KBO's.  Unfortunately, my daughter has a name from greek mythology and her name had already been used a couple of times (one of which was an asteroid) :).
I'm not completely sure about more distant objects but usually they just receive a catalog designation that is used, there tend to be too many for names for every specific one.
The features on the Moon are named for famous scientists and in a few cases other notable persons from earth.  The near side features come from all over while the far side features are primarily named for Russian/Soviet figures as the Soviet Union was the first to put a probe in orbit around the Moon and actually obtain images of that side of the Moon.
A: There are many different procedures for different classes of objects. Nowadays so many discoveries are being made that most are just given catalog numbers of one kind or another. The IAU is the clearing house for most names; names are usually assigned within a few days of discovery. For example, the supernova in Messier 51 discovered last week was named 2011dh a few days after it was discovered. Many modern names incorporate the year of discovery or the object's coordinates on the celestial sphere.
Names of features on the Moon and Mars were originally assigned by visual astronomers in earlier centuries. Craters on the Moon, for example, are named after deceased astronomers or other scientists, the only exceptions, named after living people, being the craters named for astronauts who visited the Moon. It makes me feel old when I realize that there are craters on the Moon named after three people I actually knew when they were alive: Beals, Leakey, and Peek!
Names on mars are based on maps made in the 19th century, but have been enhanced by our newer knowledge of actual topography.
A: The IAU is responsible for naming conventions and certifying proposed names. There are certain themes for different classes of objects- all new features on Venus must be named after women, the moons of Uranus are named after Shakespeare characters, kuiper belt objects are named after deities, etc. It is usually the discoverer who chooses the name to be certified by the IAU.
Astronomical objects known to humanity since before the IAU developed this procedure, including many surface features of the front of the Moon, often have historical names that defy their later convention. Now, maria on the Moon are typically given Latin names of abstract, positive nouns, e.g. Mare Tranquilitatis, "Sea of Tranquility." Craters are named after astronomers. Large Martian surface features have Latin names, e.g. Olympus Mons, "Mount Olympus," also consistent with the earliest observations of Mars occurring when Latin was the lingua franca of science.
http://www.iau.org/public/naming/
http://en.wikipedia.org/wiki/Category:Surface_features_of_Mars
