Ben Zimmer at Visual Thesaurus:
Some have theorized that Ms. has roots long before the 20th century. One piece of evidence that has been put forth is the tombstone of Sarah Spooner, who died in 1767 in Plymouth, Massachusetts. As you can see from this image, what appears on the headstone is M with a superscript s. As Dennis Baron writes in his excellent book Grammar and Gender (1987), “it is certainly an abbreviation of Miss or Mistress, and not an example of colonial language reform or a slip of the chisel, as some have suggested.”
There things stood until 2004, when I happened upon this tantalizing little notice in the Humeston (Iowa) New Era of Dec. 4, 1901 (thanks to the Newspaperarchive database):
The writer seems confused about the Springfield Republican proposal since he (or she, but probably he) guesses that Ms. is an abbreviation of some longer word. That's a confusion that persists among those who assume Ms. is an abbreviated form of Miss or Missus, but the Republican article puts forth Ms. without any particular expansion.
More here.