First of all, rhyming in poetry goes back to time immemorial, our earliest example coming from the Chinese Shi Jing ca. 10th century BC. We really don't have a great sense of how poetic features like rhyme interacted with music here, simply because so little of the musical tradition survives. But as one instance, Hebrew "songful" music, like the psalms, did not tend to employ rhyme as a common poetic device. On the other hand, the Seiklos epitaph, one of our earliest complete musical pieces, does seem to contain some sort of rhyme scheme (though I am by no means an expert on Greek pronunciation

Ὅσον ζῇςφαίνου
μηδὲν ὅλωςσὺ λυποῦ
πρὸς ὀλίγονἐστὶ τὸ ζῆν
τέλος ὁχρόνοςἀπαιτεῖ

The final words of each line, using the IPA for 1st century CE Egyptian Greek, are

ζῇςφαίνου = /ˈpʰɛ.no/
λυποῦ = /lyˈpɛ.o/
ζῆν = /ˈza.o/
ὁχρόνοςἀπαιτεῖ = /a.pɛˈtɛ.o/

So here, at least. There does seem to be some kind of rhyme scheme going on, especially the /ɛ.o/ endings of lines 3 and 4

The rest of my post will deal with the tradition of Western Classical music, the music we have probably the most secure historical understanding of.

The tradition of gregorian chant, which in turn served as the basis for much of western music making until at least the Renaissance, was based on Latin versions of the bible, which mostly did not make explicit use of rhyme schemes except insofar as Latin naturally produces rhyming through its syntactical structure (like "Notum fecit Dominus salutare suum; / ante conspectum gentium" from the chant Viderunt omnes, which mostly seems to be a byproduct of the tense used in the verse rather than an explicit poetic rhyme).

But it's in secular song where we really see rhymed verse take off. The French Troubadours and Touveritzes of ca. the 13th century, for instance, employed rhymed verse all the time. Here's the poetry for Beatriz de Dia's lively "A chantar m'er:"

A chantar m'er de so qu'eu no volria,
tant me rancur de lui cui sui amia;
car eu l'am mais que nuilla ren que sia:
vas lui no.m val merces ni cortezia
ni ma beltatz ni mos pretz ni mos sens;
c'atressi.m sui enganad' e trahia
Com degr' esser, s'eu fos dezavinens.

The obsession with "-ia" rhymes could not be more obvious here, it is broken only by the "-ens" rhymes that mark the 5th and 7th phrases.

Secular traditions like these seem to be the way that rhyming is propagated throughout European music making, at least. In the 14th century, these regular rhythmic and rhyming properties were codified into sets of standard forms, called the formes fixes or "fixed forms," which controlled not only rhythm and broad repetition schemes, but also rhyme schemes (the "Ballade," for instance, had an ABABBCBC rhyme structure). These are the sorts of impulses that underpin the Western obsession with rhyming song that we still feel today.