Where does the phrase "makes sense" come from?

The expression make sense dates back to the 17th century:

• Be reasonable, wise, or practical, as in It makes sense to find out first how many will attend the conference. This term employs sense in the meaning of "what is reasonable," a usage dating from 1600. In Britain it is also put as stand to sense.

• Be understandable. This usage, first recorded in 1686, is often used in a negative context, as in This explanation doesn't make sense.

(AHD)

Note that "sense":

• Meaning "that which is wise" is from c. 1600.

(Etymonline)

To add a little bit to Josh's answer, OED provides three definitions for to make sense. While the earliest attested uses date back to 1554 (albeit without the word make), it seems that the most common forms people use contemporarily when they say "makes sense" are from definitions (b) and (c) below.

(a) With written or spoken language as subject: to be coherent or intelligible. Formerly also in the same sense: †to have (also) give) sense. In later use also with a person as subject: to speak in a manner that is coherent or intelligible.

The earliest attested use of this definition is from 1554, but it does not use the construction "make sense."

1554 J. Gwynneth Manifeste Detection of Notable Falshed f. 27 This worde..muste nedes bee referred to somewhat, before or after, or els it can haue no sence.

We find "make" used with "sense" attested in 1721.

1721 A. Malcolm Treat. Musick xiv. 538 This, to make any Sense, must signify that [etc.].

---

(b) In extended use: to be intelligible or comprehensible, esp. in the context of pre-existing knowledge or expectations. Frequently in negative constructions, and with non-referential it as subject.

Here we have a definition that seems to me to more directly apply to the way "makes sense" is used frequently today. It fits well with the ngram provided in the question. The earliest attested use of this definition is from 1905.

1905 E. M. Forster Where Angels fear to Tread i. 20 ‘I don't understand,’ she said; ‘it doesn't make sense.’... ‘The meaning is quite clear,—Lilia is engaged to be married.’

---

(c) To be sensible, advisable, or viable, esp. as course of action. Frequently with it as subject and followed by to. Also followed by as

Unlike definition (b), this one is not usually used in negative constructions. Earliest cited uses are from the 1930's.

1931 Time 15 June 24/2 He would never undertake the ‘Christian’ daily unless it made sense as a newspaper.

1937 Pop. Sci. Monthly Oct. 117/1 It makes sense to have half the length ground straight.

---

To some extent, NGram searches provide support for the notion that "to make sense" was mostly prevalent in negative constructions before its affirmative use. This chart should be taken only as a supplement to the descriptions offered by OED and other sources, because the terms being compared are not of identical construction. Still, the rapid split between "does not make sense" and "makes sense" in the span of a decade fits with the notion that to make sense was more prevalent earlier in a negated form. The timing of the divergence seems to follow with only slight delay the attested dates OED provides as a distinction between definition (b) (often negated) and definition (c) (not necessarily negated).

(Note that NGram treats "doesn't make sense" as equal to "does not make sense.)

I would offer the concept of making “cents” meaning a clear line to profit. If something makes sense to me that would mean that it is practical and easily replicated. Always with the emphasis on the benefit.