The History of Last Names
Did your grandparents have a middle name? If they did, chances are their parents didn't. The three name system that is fairly standard among the English speaking countries is a relatively recent development. Still -- it wasn't just invented. The Romans had an elaborate three name system that fell along with the Empire, and by the fourth century AD there was nary a middle or last name to be found.
Single names worked as well as can be expected for the next six hundred years. The practice of attaching a word to help identify a man was resurrected in Venice and spread first to France, then England, then Germany -- then to the rest of Europe. (Most of Europe, anyway...) Today, those without a surname are the exception, and even Cher , Madonna , and Sting started out with a last name!
The Chinese were the first to adopt surnames to honour their forebears, with the family name placed first, rather than last. Thus, the family name of Sun Yat-sen is Sun. Surnames that describe a man by his relatives are only one of the several categories of surnames.
When communities consisted of just a few people, surnames weren't so important. But as each town acquired more and more Johns and Marys, the need was established for a way to identify each from the other. The Romans had begun the practice of using "given-name + clan-name + family-name" about 300 B.C. In the English-speaking part of the world, the exact date that surnames began to be 
adopted can't be pinpointed. The Domesday Book compiled by William the Conqueror required surnames, but hereditary surnames are not considered to have been commonplace until the late 1200's.
William Camden wrote in Remaines of a Greater Worke Concerning Britaine:(1586)
About the yeare of our Lord 1000...surnames began to be taken up in France, and in England about the time of the Conquest, or else a very little before, under King Edward the Confessor, who was all Frenchified...but the French and wee termed them Surnames, not because they are the names of the sire, or the father, but because they are super added to Christian names as the Spanish called them Renombres, as Renames.
Categories of Names
Some surnames were derived from a man's Occupation (Carpenter, Taylor, Brewer, Mason), a practice that was commonplace by the end of the 14th century. Place names reflected a location of residence and were also commonly used (Hill, Brook, Forrest, Dale) as a basis for the surname, for reasons that can be easily understood. Some place names are a little cryptic, such as Chevrolet, the French place name that means "little goat." The name referred to the picture painted on the outdoor sign at a roadside inn. Pictures were used since few had reading skills, and in that era, chevrolet referred to a place. Sometimes a man was most easily distinguished among his neighbours by a particular trait, or by some physical characteristic. Nicknames that stuck became surnames -- some of which were so vicious, it is surprising they lasted at all. Many with names vulgar or scurrilous connotations were eventually changed by altering the spelling, or just dropped outright in favour of a more acceptable monicker. About one-third of all US surnames are Patronymic in origin, and identified the first bearer of the name by his father (or grandfather in the case of some Irish names). Acquired Ornamental names were simply made up, and had no specific reflection on the first who bore the name. They simply sounded nice, or were made up as a means of identification, generally much later than most surnames were adopted. There are other sources as well, but most can be wedged into one of the above categories -- one way or another.
When surnames were being adopted, many were the result of nicknames that were given by friends, relatives, or others. Some nicknames were extremely unflattering -- to the point of vulgarity -- but most of those have vanished, having been changed by descendants through spelling changes or simply by changing names after emigrating.
Physical features that were prominent when surnames began to be adopted were also borrowed as an identifier (Long, Short, Beardsly, Stout) as were dispositions of the bearers (Gay, Moody, Sterne, Wise). Sometimes the name told its own story (Lackland, Freeholder, Goodpasture, Upthegrove) and sometimes they might have been selected to elicit envy or sympathy (Rich, Poor, Wise, Armstrong).
Patronymic and Matronymic
Names that identify the father are termed Patronymic surnames. Rarely, the name of the mother contributed the surname, which is referred to as Matronymic origin. The Scandinavians added "son" to identify John's son or Erik's son. The Norman-French used the prefix "Fitz" to mean child of, as in Fitzpatrick, for child of Patrick. Many other cultures had their own prefixes to indicate of the father ('s name) , including the Scots ('Mac'Donald), Irish ('O'Brien), Dutch ('Van'Buren), the French ('de'Gaulle), Germans ('Von'berger) Spanish/Italian ('Di'Tello) and the Arab-speaking nations ('ibn'-Saud). Sometimes the prefixes were attached to places rather than the father's name, such as traditional family land holdings or estates.
Acquired and Ornamental
Some names were simply added when those without a surname suddenly needed one. A lady-in-waiting for royalty might have had no traditional surname, but would require one if no longer in the service of royalty. In times of political turmoil, a deposed ruler might require a smaller staff, and long-time servants would find themselves among commoners -- and suddenly in need of a surname. Names were sometimes invented as combinations of other words.
Among the most common names are those specialty crafts and trades that were common during medieval times. The Miller was essential for making flour from grain. The Sawyer cut timber into workable lengths, with which the Carpenter could make specialty items for villagers. Some names were a reflection of the place of employment rather than the job itself -- the name Abbott generally refers to the man who was in the employ of the abbey as a servant or other worker; the man named Bishop more than likely worked at the house of the Bishop rather than holding the position. Some names were taken as titles that were originally less occupational, such as Mayor. Some surname occupations are no longer in existence but were enough to identify a man in medieval days.
The most widely found category is that which contains surnames derived from a place easily recognizable when surnames were adopted. When a man left his homeland and moved to another country, he was distinguished from his neighbours by the identity of his homeland -- Walsh hailed from Wales, Norman was from Normandy, Norris was Norwegian. Some men were from cities well-enough known that the city was the distinguishing reference as in Pariss. Towns were used in the same fashion, as were major rivers and geographic features. Less obvious now are those names which identified a man by the location of his house. John Atwood lived at the woods, but exactly which one has long since been lost. Other names can be traced to the exact locale where the first to bear the name kept his residence. As with the Patronymic designators, languages varied in the way a place was denoted, as in the Dutch name Van Gelder (from the county of Gelder). The Germans used Von as the French used de or De, and both often reflected aristocracy.
Sources include but are not limited to: American Surnames by Elsdon C. Smith, Baltimore, 1969; A Dictionary of Surnames , by Patrick Hanks and Flavia Hodges, New York, 1994; Family Names: How Our Surnames Came To America , by J. N. Hook, New York, 1982