The cross as a symbol of Christianity and as a central image in people's interpretation of the Gospels is a great example of how the meaning of words have developed over time, disconnecting modern Christianity from its roots in Christ's teaching. The "cross" as it is known today was have been completely unknown in Christ time and in the centuries after.
People in Christ’s times not have understood the translation of Mat 16:24 as we translated it today: “If any [man] will come after me, let him deny himself, and take up his cross, and follow me.” (click to see Greek). They would not have had any context for “taking up a cross” because Christ had not carried his “cross”. Christ was saying something completely different then that had nothing to do with this symbol.
Instead, his audience would have heard this as the much more understandable: “If anyone wishes to make his way after me, let him reject himself and pull up his stake and be guided by me.” The “stake” referred to the center pole of tent, and the phrase, then as now, was an analogy for being willing to move from where you were to somewhere new. However, Chris also knew that he would die on a pole. So his use of this metaphor was a play on words.
The conversion of the word to "cross" started first in the Latin Vulgate, the translation of the Bible into Latin. It translated the Greek stauros into the Latin crux. This word is our phonetic basis for the word "cross" but crux did not mean "cross" either, not as we use it today. It was the Latin word for the form of torture used to kill Christ. It referred to the stake. Its verb form, crucio, means simply "to torture."
So, where did the form of the cross, an upright pole with a crossbar, come from. The early symbols (2nd century) of Christ were a dove, a fish, a ship, a lyre, and an anchor. The Greek letter chi, which looks like the letter X is the first letter of the Greek word from Christ, χριστός. We see early uses of the various Christ symbols with the "X", two fish forming an "X", or the anchor, with its crossbar leaning into an "X.
The symbol of the X grew in popularity with its adoption by Constantine, the first Christian emperor's use of the chi-ro (which look like a P with an X across the descender of the P) on his banner and the painting of the X on his men's shields. This chi-rho image was seen symbolic representation of the head, arms, and legs of an upright stake. Over time, this image was simplified into the cross we know today.
The earliest image of Christ hanging on a cross was used to decorate a reliquary around AD 420 among The Maskell Ivories of British Museum. See this article tracing the evolution these images.