Here's the history of Ash Wednesday from americancatholic.org:
Although Ash Wednesday is not a Catholic holy day of obligation, it is an important part of the season of Lent. The first clear evidence of Ash Wednesday is around 960, and in the 12th century people began using palm branches from the previous Palm Sunday for ashes.
Our Shifting Understanding of Lent
Those who work with liturgy in parishes know that some of the largest crowds in the year will show up to receive ashes on Ash Wednesday. Though this is not a holy day of obligation in our tradition, many people would not think of letting Ash Wednesday go by without a trip to church to be marked with an ashen cross on their foreheads. Even people who seldom come to Church for the rest of the year may make a concerted effort to come for ashes.
How did this practice become such an important part of the lives of so many believers? Who came up with the idea for this rather odd ritual? How do we explain the popularity of smudging our foreheads with ashes and then walking around all day with dirty faces? Those who do not share our customs often make a point of telling us that we have something on our foreheads, assuming we would want to wash it off, but many Catholics wear that smudge faithfully all day.
Ashes in the Bible
The origin of the custom of using ashes in religious ritual is lost in the mists of pre-history, but we find references to the practice in our own religious tradition in the Old Testament. The prophet Jeremiah, for example, calls for repentance this way: "O daughter of my people, gird on sackcloth, roll in the ashes" (Jer 6:26).
The prophet Isaiah, on the other hand, critiques the use of sackcloth and ashes as inadequate to please God, but in the process he indicates that this practice was well-known in Israel: "Is this the manner of fasting I wish, of keeping a day of penance: that a man bow his head like a reed, and lie in sackcloth and ashes? Do you call this a fast, a day acceptable to the Lord?" (Is 58:5).
The prophet Daniel pleaded for God to rescue Israel with sackcloth and ashes as a sign of Israel's repentance: "I turned to the Lord God, pleading in earnest prayer, with fasting, sackcloth and ashes" (Dn 9:3).
Perhaps the best known example of repentance in the Old Testament also involves sackcloth and ashes. When the prophet Jonah finally obeyed God's command and preached in the great city of Nineveh, his preaching was amazingly effective. Word of his message was carried to the king of Nineveh. "When the news reached the king of Nineveh, he rose from his throne, laid aside his robe, covered himself with sackcloth, and sat in the ashes" (Jon 3:6).
In the book of Judith, we find acts of repentance that specify that the ashes were put on people's heads: "And all the Israelite men, women and children who lived in Jerusalem prostrated themselves in front of the temple building, with ashes strewn on their heads, displaying their sackcloth covering before the Lord" (Jdt 4:11; see also 4:15 and 9:1).
Just prior to the New Testament period, the rebels fighting for Jewish independence, the Maccabees, prepared for battle using ashes: "That day they fasted and wore sackcloth; they sprinkled ashes on their heads and tore their clothes" (1 Mc 3:47; see also 4:39).
In the New Testament, Jesus refers to the use of sackcloth and ashes as signs of repentance: "Woe to you, Chorazin! Woe to you, Bethsaida! For if the mighty deeds done in your midst had been done in Tyre and Sidon, they would long ago have repented in sackcloth and ashes" (Mt 11:21, Lk 10:13).
Ashes in the History of the Church
Despite all these references in Scripture, the use of ashes in the Church left only a few records in the first millennium of Church history. Thomas Talley, an expert on the history of the liturgical year, says that the first clearly datable liturgy for Ash Wednesday that provides for sprinkling ashes is in the Romano-Germanic pontifical of 960. Before that time, ashes had been used as a sign of admission to the Order of Penitents. As early as the sixth century, the Spanish Mozarabic rite calls for signing the forehead with ashes when admitting a gravely ill person to the Order of Penitents. At the beginning of the 11th century, Abbot Aelfric notes that it was customary for all the faithful to take part in a ceremony on the Wednesday before Lent that included the imposition of ashes. Near the end of that century, Pope Urban II called for the general use of ashes on that day. Only later did this day come to be called Ash Wednesday.
At first, clerics and men had ashes sprinkled on their heads, while women had the sign of the cross made with ashes on their foreheads. Eventually, of course, the ritual used with women came to be used for men as well.
In the 12th century the rule developed that the ashes were to be created by burning palm branches from the previous Palm Sunday. Many parishes today invite parishioners to bring such palms to church before Lent begins and have a ritual burning of the palms after Mass.