Mr. and Mrs. derive from Master and Mistress - generic positions of authority within a household or other establishment from late Middle English. Since a woman would typically come by such authority only through a marriage, the connection between "mistress" and "married woman" was implied.

"Mister" as a weaker form of "master" was in use by the mid 16th century to address any man who did not have a formal or professional title. "Master Smith," which is how you would address someone who was literally a master blacksmith, became Mister Smith. (Incidentally, this is how we got a lot of modern surnames.) The abbreviation Mr. was already in use for master, and was inherited.

Mrs. was used as an abbreviation for Mistress from the early 1600s. It was in the 1700s that "miss" came about as a diminutive form of mistress, in specific context with age (the young miss). "Missus" as a specific reference to a married woman completely divorced from the concept of eminence or authority didn't turn up until the late 1700s, and it inherited Mrs.

"Miss" firmed up as a formal style of address for unmarried women in the latter part of the 1700s in England, when society in general was firming up the rigid rules regulating order-of-precedence amongst untitled people. Unmarried women were further specified by their status within their own households - eldest daughters were Miss Lastname, subsequent daughters were addressed as Miss Firstname. Formal full address in either instance was Miss Firstname Lastname, which eventually conformed to the Title/Honorific Lastname style of address used by everyone else.

TL;DR: They mean different things. Mrs./Miss came to denote married/unmarried status long after men were already using Mr.