How did the cross come to be a symbol for Christianity? I understand WHY the cross became a symbol for Christianity, but HOW did it become a symbol?  How did it start and how did it evolve into the symbol (or symbols since there are many variants) we all know today?
The first chapter of John Stott's The Cross of Christ provides a history of the development of the use of the symbol of the cross in Christianity.  I'll briefly summarize it here.
Pre-cross images
The earliest images used by Christians did not include the cross. Persecution required that they be circumspect, which meant that an image clearly associated with both Christ and execution could not be preferred.  Thus, the earliest images included peacocks, doves, and particularly fish.  The greek word for fish, ichthys, served as an ancronym for Iesus Christos Theos Huios Soter (&quot;Jesus Christ, Son of God, Saviour&quot;), which drew less attention from the uninitiated.
Second-century images included biblical scenes like Noah's ark, Abraham killing the ram, and the raising of Lazarus.  These had a closer relationship to the redemption of Christ, but were still not obvious enough for the public at large to understand the reference.
Choosing the cross
Christians had a variety of emblems to choose from, such as the manger where Jesus was born, or the boat from which he taught, or the stone that rolled away from his grave.  But, says Stott, Christians wanted to:

commemorate as central to their understanding of Jesus neither his birth nor his youth, neither his teaching nor his service, neither his resurrection nor his reign, nor his gift of the Spirit, but his death, his crucifixion.

The cross image at this time was not a crucifix, that is, a cross with Jesus' body on it; such images apparently arrive in the sixth century. (for more on this, see When did the split in crufix/empty-cross symbolism occur?)
Early use of the cross
Stott argues that the cross was in use by the 2nd century.  He interprets Tertullian's  AD 200 writing, &quot;we trace upon the forehead the sign,&quot; as being the sign of the cross (De Corona, chapter 3).  He also presents the writing of Hippolytus (The Apostolic Tradition, AD 215):

He mentions that the sign of the cross was used by the bishop when anointing the candidate's forehead at Confirmation [...] [i]t is also, he adds, a protection against evil.

Hippolytus, says Stott, was a conservative who would not have been describing rites and customs unless they were &quot;already long-established,&quot; perhaps a generation or more.
Additional evidence from the early church comes from Cyprian, in the middle of the third century, who also appears to make reference to the symbol of the cross in his work De Lapsis.
Constantine
Constantine famously propelled the use of the cross as a symbol when he reportedly saw a vision at the Battle of the Milvian Bridge.  The vision showed a cross and the words, &quot;Conquer by this sign.&quot;  The subsequent victory inspired Constantine's conversion, and he began using the cross on the standards of his army.  The cross thus became widely known across the Roman Empire as the symbol of Christianity.