Actually, most of the new words appears to have based on existing words to some extent: either taking a noun and turning into a verb or vice versa (one example of this would be "to dawn"), or shortening a word or adding a new beginning ending ("irregulous"), or joining two words together ("eyeball"): all these would be rather easily understood.
More difficult, but not impossible for at least parts of his audience, would be borrowing words from other languages, especially Latin.
These would have covered the majority of his new words. There were a few exceptions, but some of those are onomatopoeia, such as "gnarling". Ther remains a very few beyond that, and for those, such as "potch" (Coriolanus: "I'll potch at him some way"), we have to remember that some sounds actually have a sort of meaning. Take "slimy", "slither" and "sliding": it would seem that "sli" suggest a certain meaning, so a hypothetical word formed with that combination ("slinny") would suggest something similar. Context would also help. If you really want to see how one can "understand" a totally new word, I would suggest reading some nonsense verse, such as Jabberwocky.
Sources
I found this to be a useful overview of words first appearing in Shakespeare; from the same site is a more in-depth coverage of how he coined words (at the end of which are a few entirely new words). For the meaning of sounds, this Wikipedia article gives some introduction (I have also read about it in books on linguistics, but those were in Swedish).