Signatures are required on many documents; what is the history of this
requirement and where and when are signatures needed? References would
be appreciated.

Just a free comment:
The signature (or "mark") signifies that the person involved
agrees/approves/issues the document.  I add "mark", since analphabets
can also "sign" a document without being able to write their name,
which these days has to be witnessed.  In early medieval times, many 
- including rulers -  could not write.  A personal seal serves a
similar purpose, less common in the West today, but in the Far East
still not uncommon.
This site may be of help, but I expect that there are much more informative ones:
http://www.arikah.com/encyclopedia/Signature

Here is an auction site's image of Charlemagne's signature:
http://img.yezzz.com/fi3121428.jpeg

I seem to remember reading that he only added a final stroke or two to it.

Elaborate signatures not only show individuality but also are/were an
attempt to make forgery more difficult.  In the Orient, I have seen
pilgrims use their thumbprint to "sign" travelers checks.