The Catholic Encyclopedia says:
The cross was originally traced by Christians with the thumb or finger
on their own foreheads. This practice is attested by numberless
allusions in Patristic literature.
It's unclear when it began, but it's true there are "numberless allusions" indicating it was an early and widespread tradition. For example, Tertullian:
At every forward step and movement, at every going in and out, when we
put on our clothes and shoes, when we bathe, when we sit at table,
when we light the lamps, on couch, on seat, in all the ordinary
actions of daily life, we trace upon the forehead the sign.
It's been associated with Revelation 7:
Then I saw another angel come up from the East, holding the seal of
the living God. He cried out in a loud voice to the four angels who
were given power to damage the land and the sea, “Do not damage the
land or the sea or the trees until we put the seal on the foreheads of
the servants of our God.” I heard the number of those who had been
marked with the seal, one hundred and forty-four thousand marked from
every tribe of the Israelites.
Catholic commentators associate the seal on the forehead with the sign of the cross. This goes back to Ezekiel 9:4.
Lord said to him: Pass through the city, through the midst of
Jerusalem, and mark … the foreheads of those who grieve and lament
over all the abominations practiced within it.
The mark spoken of here is "tau," a Hebrew letter in the shape of a cross.
The Catholic Encyclopedia also says that it wasn't long before Christians began making the sign of the cross on things other than foreheads:
Hardly less early in date is the custom of marking a cross on objects
— already Tertullian speaks of the Christian woman "signing" her bed
(cum lectulum tuum signas, "Ad uxor.", ii, 5) before retiring to
rest—and we soon hear also of the sign of the cross being traced on
the lips (Jerome, "Epitaph. Paulæ") and on the heart (Prudentius,
"Cathem.", vi, 129). Not unnaturally if the object were more remote,
the cross which was directed towards it had to be made in the air.
Thus Epiphanius tells us (Adv. Hær., xxx, 12) of a certain holy man
Josephus, who imparted to a vessel of water the power of overthrowing
magical incantations by "making over the vessel with his finger the
seal of the cross" pronouncing the while a form of prayer. Again half
a century later Sozomen, the church historian (VII, xxvi), describes
how Bishop Donatus when attacked by a dragon "made the sign of the
cross with his finger in the air and spat upon the monster".
As for the purpose, Athanasius quotes Antony as saying:
When, therefore, [demons] come by night to you and wish to tell the
future, or say, "we are the angels", give no heed, for they lie. Yea
even if they praise your discipline and call you blessed, hear them
not, and have no dealings with them; but rather sign yourselves and
your houses, and pray, and you shall see them vanish. For they are
cowards, and greatly fear the sign of the Lord's Cross, since of a
truth in it the Savior stripped them, and made an example of them. ...
But we by the mention of Christ crucified put all demons to flight,
whom you fear as if they were gods. Where the sign of the Cross is,
magic is weak and witchcraft has no strength.
Conclusion: The sign of the cross originated early, growing out of an interpretive seed found in Revelation and Ezekiel. It's a way of invoking the power of the cross against the enemies of God.