How do I decipher the results of a validator?
The key to understanding them is the HTML syntax. The formalized syntax (which is really what a validator checks) is not as difficult as it looks like, but it requires some SGML literacy to read it.
Simpler explanations of the syntax are usually sufficient for understanding the syntax errors. The WDG material is very useful as a quick reference to the syntax (see especially the "Contents" and "Contained in" parts in the element descriptions as well as the attribute descriptions).
For example, if you have
<font face="Arial">foo bar <p>some text ...
(a rather common syntax error I'd say) and you get an error message (you should!), then start from the description of the valid contents of <font> elements. Only "inline" elements are allowed there. Some quick study of what "inline" means (as explained in the WDG material) hopefully tells that <p> is not inline. So you need to close the <font> element (with </font>) before <p>. The principle is that markup like <font> is inline, or text level, and cannot contain paragraphs or other block-like constructs.
Similarly, if you get an error message for
<table><td>...
then you should look at a description of what a <table> element may contain. You'll find out that it may not _directly_ contain <td> elements but only inside <tr> elements, so you need to add <tr> markup. (Once you get used to it, it's pretty logical: a table consists of rows that consist of cells; hence, a cell cannot _directly_, outside any row, appear inside a table.)
Note that as in all checking of data, an error might create other error messages in the sequel even if the rest is OK, because an error often causes the rest get out of proper context. The general idea is to proceed stepwise when fixing errors: start from the first error messages and fix as many problems as you can understand, then validate again. Quite often you'll see one correction remove lots of error messages.
You might also try the WDG validator which has somewhat more explanatory error messages than the W3C validator. (The messages contain links to explanations that might be useful too.)