Marthiya (eulogies, lamentation poetry) for Imam Husayn (A) probably began soon after his martyrdom, since the custom of reciting marthiya in Arabic existed before his time, and was a custom shared by many people, not just Shi'is. Often, marthiya was recited by the mother, sister, or daughter of the deceased, although it was also done by men. 

In the maqtal literature (accounts of the martyrdom of Imam Husayn), it is related that several survivors of the Battle of Karbala recited lamentation poetry for him. For instance, it is related that Rabab, the wife of Imam Husayn (A), used to recite this lament (translation by Yasin Jibouri), while applying herbs to her eyes to make herself cry more: 

The one that used to be a lantern
Is now at Karbala’, killed, unburied.
O grandson of the Prophet! May Allah
Reward you on our behalf and may you
Never fall short of the Scales.
A great mountain you used to be
A shelter, secure, for me,
And a companion in family
And in faith a surety.
Now who shall for the orphans be
Of help, and who shall be for the needy?
Who shall be the resort of the destitute?
By Allah! Never shall I seek
For you at all any substitute,
Till between the sands and the mud is my abode
Wherein I will be hidden from the world. (Abul-Faraj al-Isfahani, Al-Aghani, Vol. 2, p. 158)

After that, there are narrations in which Imam al-Baqir (A) and, later, Imam al-Sadiq (A) praise a poet named Kumait for eulogizing Imam Husayn (A) in poetry.

One of the famous poets who supported Ahl al-Bayt (A) in the time of Imam Kazim (A) and Imam Rida (A) was Di'bil al-Khuza'i, who wrong a long poem on the sufferings of Ahl al-Bayt (A). Here is a short section of it:
 

O Fatima, had you seen Husayn fallen,
Lifeless, thirsty, by the flowing Euphrates' shore
You would have struck your cheeks in anguish, O Fatima, beside him
Tears streaming down your face.
Rise, O Fatima, O daughter of divine grace;
Mourn the stars of the heavens fallen in this desert land.
With some graves in Kufa, and others in Medina
And others in Fakh, hallowed by my prayers.

أفاطم لو خلت الحسين مجدلا

وقد مات عطشانا بشط فرات

إذا للطمت الخد فاطم عنده

وأجريت دمع العين في الوجنات

أفاطم قومي يا ابنة الخير واندبي

نجوم سماوات بأرض فلاة

قبور بكوفان واخرى بطيبة

واخرى بفخ نالها صلواتي

So these are some early examples of lamentation poetry for Imam Husayn (A).