The Grove Dictionary says:

A French word meaning ‘again’, cried out by English audiences (not French ones, who use bis) to demand the repetition of a piece just heard or an extra item. This use of the word goes back at least to February 1712, when it attracted satirical comment in the Spectator: ‘I observe it’s become a custom, that whenever any gentlemen are particularly pleased with a song, at their crying out encore or altro volto, the performer is so obliging as to sing it over again’. In this period, the word had a fashionable status. Pope (1742) has the ‘harlot form’ of Opera telling Dullness (‘in quaint Recitativo’): To the same notes thy sons shall hum or snore And all thy growing daughters cry encore. (The Dunciad, iv. 59). In both concerts and operas the progress of a work was freely interrupted for the repetition of arias or movements. Today, an ‘encore’ usually means an extra piece played at the end of a solo or chamber recital, or by a soloist after a concerto, in response to more than perfunctory applause. If American audiences cry out, it is usually ‘bravo’, not ‘encore’. PETER WALLS

It's one thing for the audience to ask for some more music, and another for the performer to exit the stage.

The asking for more music had a difference sense because it was at first about getting to listen one more time (or several times) some of the music performed at that event. See, most music was played once or twice and that was pretty much it. Today we listen to a lot of works very often, but concerts were about new music most of the time. So getting to listen to something particularly nice again was a treat.

Now, exiting the stage has to do with the ritual of public performance. I am not sure about when that started, but it is probably around the time big venues started to become common for this kind of event (the 19th century). It's about gestures and drama... It's a strange ritual from a time very different from ours.