To summarise: "note" has the general meaning of "quality", "character", or "tone", developing from the musical sense of "note". "On" means in accordance with a pattern or style.
The OED lists this sense of note as an extension of "A single tone of definite pitch, as produced by a musical instrument, the human voice, etc." This gives rise to:
II.7.c. figurative. to strike (also hit) a —— note and variants: to express a sentiment, idea, etc., of a specified tone or character; (similarly) to strike (also hit) the right note; (also) to hit a (high, low, etc.) note: to achieve a specified level of success.
And hence on that note:
II.10.a. An expressive or significant sound. Chiefly in extended use: a quality or tone, esp. in speech or writing, which expresses a mood or attitude, or indicates the significance of the words or situation (frequently with of). Also in phrase on that note. In early use also: import, tenor. Cf. sense II.7c.
So it derives from the idea of a scale made up of various notes, and producing a specific tone from that scale.
Sense II.10.a is traced back to the 15th century, but its modern sense is more recent. One example is Thomas Hardy, 1891:
Reflectiveness passed into her face, and a note of tragedy at times into her voice.
Somerset Maugham, 1915:
Mrs. Athelney poured tea out of a lustre teapot which gave a note of England and the country-side to the festivity.
But the first use of on or upon is Ngaio Marsh in 1954:
‘And upon that note,’ said Alleyn, ���we may return to Rocqueville and make our plans.’
Or more recently, Terrorizer magazine in 2001:
On a happier note, Metallica's Lars Ulrich has proved that he does have some lead in his pencil after all.
The preposition "on" requires a bit more explanation: musical examples going far back use "with" and some kind of note, e.g. "yong men began the masse with a solempne note." (1493) "By note" in early modern English meant "from sheet music".
More relevant, "on" has the meaning "I.v.15 According to; in agreement or accordance with; in the style of, on the pattern of, after". As in "on schedule" (1909), "on the Roman pattern" (1942), or with music (1753):
Novelty of a musical Passage arises..from a melodious Variation on the same Notes.
Hence it's natural to talk about something on a particular note.