I agree with Kate Sherwood, you should be able to attribute most quotes these days by simple fact checking. I also like her suggestions for introducing the text, but you can also consider other, formal methods of citation and attribution.
In those cases where it's ambiguous as to who said it (for example, there's disagreement or debate over the true source), provide a citation using the title of a known work that references the quote, or debates who said it. Likewise, if the author is completely unknown, attribute it to the title of a work that has this saying in it, because obviously you must have used the quote from some existing source. (This would be in accordance with MLA guidelines. See "Citing an Unknown Author" for an example.)
As a last resort, perhaps attribute it to "Anonymous", and provide the estimated year the saying seems to have come into use e.g. (Anonymous, ca. 1400).
If the saying is so common as to be widely known, then the MLA guidelines state that "[y]ou do not need to give sources for familiar proverbs, well-known quotations or common knowledge. Remember, this is a rhetorical choice, based on audience. If you're writing for an expert audience of a scholarly journal, for example, they'll have different expectations of what constitutes common knowledge."