Until the 12th century, people were only called by their first names. From then on, descriptive titles or "bynames" were given, like Heinrich the Great, or Anna the Industrious One. Family names, or surnames, became widespread from the 15th century.
Typical German surnames mainly stem from the Middle Ages, and are derived from artisanal trades. The most important occupations then are the most common family names now. The last name Müller (miller) is the most common, but there are also lots of Schneiders (tailor), Fischers (fisherman), Schusters (cobbler) and Webers (weaver). Some names have also been modified: Schmied (blacksmith) has become Schmidt; Bäcker (baker) has become Becker.
The family or last name is very important in formal communication in Germany. You address adults with "Frau Müller" or "Herr Schuster", as well as with the "Sie" form. Teachers must also address high school students 16 years and older with "Sie" if they are asked to.