The practice of wearing crosses around the neck dates from the early church. The precise reason why Christians began wearing crosses has to do with martyrdom, specifically beheading. In the early centuries of the church, when many Christians were put to death as a result of confessing belief in Christ, the most common way to die (sometimes following a series of tortures) was by beheading. The wearing of the cross about the neck (and keep in mind that the cross would usually have been tucked in where nobody could see it) was a reminder to the wearer of the kind of confession he or she may be asked to give. It was also a symbol that the wearer was willing to give that kind of confession—-that the wearer would indeed confess Christ even to the point of beheading or any other kind of martyrdom.
As for the possibility of idolatry, early Christians were very careful to distinguish between idols and icons. Icons were not without precedent in the Jewish faith. God himself orders that the likenesses (in the Septuagint redaction, icons) of Cherubim be placed on the Ark of the Covenant. In addition, icons were seen as the visible confession that God had taken human flesh. That is to say, what was once inaccessible to us as an image was now accessible through the incarnation of Jesus. However, icons were viewed not as manifestation of God or an angel or one of the saints. Rather, they were seen as reflections, much in the way that a mirror reflects a likeness of the one looking into it.
The rules for iconography became refined very early in the church. At first, statues were allowed, but these were quickly dismissed as a tool of worship because they caused confusion among those converting from idolatrous, statue-worshipping religions. Despite prohibition, statues continued to be used in the west. In both the west and the east, iconographic symbols became prevalent. For example, a person holding a cross in an icon was martyred. If her hand is also turned outward, it means she refused to sacrifice to idols during her confession of faith. This was a very, very important and inspiring tool for a largely illiterate culture. Those who could not read words could learn a gospel story or the history of a particular martyr (so long as they knew the "code" of icons, so to speak) just by looking at the icon and "reading" its symbology. In fact, icons were not said to be painted but rather written. To this day, many Eastern Christians do not view either mosaics or stained glass as "proper" icons precisely because they lack the detail of symbology present in an icon made through tempura or encaustic methods.
In Greek, the word for veneration and worship are, unfortunately, the same word: prokinisis. This in part caused the relatively short iconoclastic period in the east that culminated in the 7th Oecumenical Council, where the veneration (not worship) of icons was restored. (There was another so-called 7th Oecumenical Council before this one that was iconoclastic, but it failed to have representatives from the major patriarchal seats of Christianity and so was later dismissed.) Another short iconoclast period in the east had similar results. Iconoclasm was not seen in the west as a major movement until the Protestant Reformation. Many Protestant groups today are iconoclastic in an understandable reaction to what seems to them to be idolatry on the part of their Roman Catholic brethren. I believe, however, that if both parties were more familiar with the history of icons, they would begin once again to favor the iconographic tradition of the church.
As for crosses, these are indeed a part of the iconographic tradition. Crosses were so venerated in the church that there are even early canons forbidding the placement of crosses in tile work on the floors of churches (so that they would not be stepped on!). This alone shows their respect and veneration for the cross. Some modern Christians have asserted that the cross is a hideous reminder of the death of Christ. But early Christians viewed it as the altar upon which the most beautiful sacrifice was made--a sacrifice of love made by God for his people. It is in this sense that the making of the sign of the cross over one's self continues to be for many Christian groups the sign of the friendship between God and man.
Added: It is common to read or hear that early Christians did not use or wear the cross. This is not accurate. Christians both used and wore the cross quite often. Both Tertullian and Minucius Felix (2nd century writers) refer to early Christians as "devotees of the cross" and make it clear that they used it extensively. To Felix in particular this was somewhat scandalous and strange (he was not a Christian).
To where do we attribute the idea that Christians did not use the cross? This comes from a confusion of a standard cross with a crucifix, the latter having a likeness of the body of Christ on it. The 82nd canon of the 3rd general assembly held at Constantinople (6th Oecumenical) makes it clear that while crucifixes were not unknown, they were not the most common expression of the cross. Up till that time, most crosses seem to have had a lamb in front of them to represent Christ. Commentary on the canon suggests that the practice of using the lamb started as a way to disguise the meaning of the cross from unbelievers.
As for those who wore the cross, the earliest example I can think of off the top of my head would be that of St. Anthony the Great. Sources differ as to whether the cross was worn around the neck or stitched onto his tunic. It may even be both. Of course, his was a T shaped cross (I say "of course," because many call this form "St. Anthony's cross"). Clement of Alexandria and Paulinus of Nola in the two centuries following also mention the devotion to the cross on the part of the church, so that it appears to have had a long, continuous history.
To David: as for the reference in the first paragraph, I can remember only that I was in a monastery bookstore when I read that, and am embarrassed to say that I cannot for the life of me remember the father I read it in. It is likely an obscure Greek or Syrian father of the church—-perhaps even one that has not been translated into English. I did put in an email to that monastery to help me track down the quote exactly, and I will publish it here when I hear back from them.
I am studying out of my home state and do not have my own library at my fingertips. If I did, I would have some idea of where to start looking in English. The following sources have more information on the history of the veneration of the cross (and thus may also include more information regarding the wearing of the cross):
John of Damascus (or Mansur): because he directly confronted iconoclasm, he provides a lot of earlier church history to establish precedent.
Peter of Damascus: I distinctly remember reading a passage wherein he describes the proper way the cross is to be signed over one's self. There may be more information regarding wearing the cross there. His work can be found in English in the 3rd volume (I believe) of the Philokalia.
Ignatios Brianchaninov: his works tend to cite more obscure fathers of the church. I have in my specifically the rather slim book "On the Jesus Prayer," though his work on the cup of Christ may also contain such references.
Old Baptismal Rites: many ancient baptismal rites call for the dressing of the newly illumined person in white garments. Sometimes also included are references to a crown, a girdle, or a cross. As befits such a rite, often included is an explanation for why the newly illumined is to wear these things.
St. John Chrysostom: I would be shocked if all of his works had been translated into English. To this day, I have only seen selections. As a trained attorney, Chrysostom had a knack for bringing in earlier church histories into his accounts of why Christians do particular things.
Finally, if anyone is interested, here is a site that purports to sell early Christian crosses (how early, I cannot tell). The information on the site about cross wearing is not fully accurate, but the relics look intriguing: http://www.johnbmcnamara.com/christianjewelry.htm
