Early use of the phrase '(as) clear as mud' seems to have been as an intensifier, as well as with the more recent sense of "not at all clear". Used as an intensifier, the phrase is obsolete, although the shorter phrase 'as mud' continues to be used as an intensifier, and was used as an intensifier before the appearance of 'clear as mud'.
Two appearances of '(as) clear as mud' in 1805, the earliest I could easily find, illustrate the senses. Their effectively simultaneous appearance suggests that the phrase may have been seen, or heard, before 1805.
In the 1805 Rhymes, by Octavius Gilchrist, this humorous verse employs 'clear as mud' as an intensifier, following on earlier use of 'as mud' as an intensifier:
And proves by argument (d'ye see)
'Tis clear as mud — that A's not B.
In the same year, 1805, the play John Bull, by George Colman, employs the phrase in the more contemporary sense of "not at all clear":
Frank. Damn it, fellow, don't trifle, but tell your story; and, if you can, intelligibly.
Dennis. Don't be bothering my brains, then, or you'll get it as clear as mud.
That the shorter phrase 'as mud' saw earlier use as an intensifier is attested by, for example, this couplet from the 1763 Rodondo, by Hugh Dalrymple:
What tell you me of British Blood?
I buy it just as cheap as Mud.