An early reference to a herma can be found in Aesop's (620–564 BCE) fables:
Ἐν ὁδῷ τις Ἑρμῆς τετράγωνος εἱστήκει, λίθων δ᾿ ὑπ᾿ αὐτῷ σωρὸς ἦν. κύων τούτῳ εἶπεν προσελθών “χαῖρε πρῶτον, Ἑρμεία ἔπειτ᾿ ἀλεῖψαι βούλομαί σε, μηδ᾿ οὕτω θεὸν παρελθεῖν, καὶ θεὸν παλαιστρίτην.” ὁ δ᾿ εἶπεν “ἤν μου τοῦτο μὴ ’πιλιχμήσῃς τοὔλαιον ἐλθών, μηδέ μοι προσουρήσῃς, χάριν εἴσομαί σοι· καὶ πλέον με μὴ τίμα.”
Source: Babrius collection, tale 48
Another reference that shows the statues were known at least as early as the 6th century BCE can be found in Plato's Hipparchus:
... he proceeded next, with the design of educating those of the countryside, to set up figures of Hermes for them along the roads in the midst of the city and every district town; and then, after selecting from his own wise lore, both learnt from others and discovered for himself, the things that he considered the wisest, he threw these into elegiac form and inscribed them on the figures as verses of his own and testimonies of his wisdom, so that in the first place,
Source: Plat. Hipparch. 228d
As for the origin of the statues, Herodotus tells us that the Athenians learned the production of the hermai from the Pelasgians, via the Samothracians:
These customs, then, and others besides, which I shall indicate, were taken by the Greeks from the Egyptians. It was not so with the ithyphallic images of Hermes; the production of these came from the Pelasgians, from whom the Athenians were the first Greeks to take it, and then handed it on to others.
For the Athenians were then already counted as Greeks when the Pelasgians came to live in the land with them and thereby began to be considered as Greeks. Whoever has been initiated into the rites of the Cabeiri, which the Samothracians learned from the Pelasgians and now practice, understands what my meaning is.
Source: Hdt. 2.51.1, Hdt. 2.51.2