From the Catholic Encyclopedia:
The manual act of tracing the cross with the hand or the thumb has at all periods been quite commonly, though not indispensably, accompanied by a form of words. The formula, however, has varied greatly. In the earlier ages we have evidence for such invocation as "The sign of Christ", "The seal of the living God", "In the name of Jesus"; etc. Later we meet "In the name of Jesus of Nazareth", "In the name of the Holy Trinity", "In the name of the Father and of the Son and of the Holy Ghost", "Our help is in the name of the Lord", "O God come to my assistance". Members of the Orthodox Greek Church when blessing themselves with three fingers, as above explained, commonly use the invocation: "Holy God, Holy strong One, Holy Immortal One, Have mercy on us", which words, as is well known, have been retained in their Greek form by the Western Church in the Office for Good Friday.
Thus, it seems the formula has varied according to place, time, and probably the occasion. It has not been accompanied by words all the time either.
Regarding the actual sign, the same source tells of different methods:
The course of development seems to have been the following. 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, and it was clearly associated in idea with certain references in Scripture, notably Ezekiel 9:4 (of the mark of the letter Tau); Exodus 17:9-14; and especially Apocalypse 7:3, 9:4 and 14:1. 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". All this obviously leads up to the suggestion of a larger cross made over the whole body, and perhaps the earliest example which can be quoted comes to us from a Georgian source, possibly of the fourth or fifth century.