Musicians had many ways of fleshing out monophonic music. One of the most documented was the English practice of turning a single melodic line into choral polyphony. We have an early example in the very famous Sumer is icumin in rota or round.
Here is the first line in the original notation:
|Click to enlarge|
Each subsequent voice enters at the spot marked with the red cross. In addition to the round part (instructions on the score call for four singers) there are two, two-measure accompaniments that flow back and forth between F and G harmonies. From other evidence, it seems that this is merely the tip of the iceberg and that there was a well-established tradition of extemporaneous choral singing, especially in England.
No-one knows how far back this and other kinds of polyphony might go. But from around the turn of the millennium in the year 1000, steadily over the next five hundred years the ability to write down polyphonic music precisely grew steadily until we arrived at our modern system of notation, which, barring some small improvements, was complete by the end of the 16th century. But we should always be aware that there has always been a huge non-literate musical culture. Where literacy helped was in the construction of more elaborate compositions--and even more importantly the ability to set them down in a way that made them easy to learn and perform not only by musicians in the same town, but by ones spread across Europe. The transmission of music was hugely aided by notation.
But now we seem to be moving into what one might call a "post-literate" era in which more and more listeners, performers and even composers do not read music. Popular musicians may or may not read music, but some of the most famous, such as John Lennon and Paul McCartney, have said on many occasions that they have never learned and never felt the need. The development of recording technology has replaced a great deal of what music notation provided. Instead of a possibly misleading notation, we have an exact, more or less, record of exactly how the piece sounds. I suspect that this transition may have consequences that we have yet to be aware of...