As we approach Christmas, we enter one of the two (the other is Easter) periods of the year in which large numbers of people claim that all popular Christian things are really pagan things. Some of this is perhaps Puritan hangover; some early Protestants refused to celebrate Christmas because they read the symbolism as Catholics acting like pagans. If you have a religion of almost pure text and moral discipline, you naturally read any substantive symbolism as a sort of heathenry. Some of it is out-of-date anthropology still floating around. It's this that gives us the entirely unsubstantiated notion that the eggs and bunnies of Easter trace back to pagan fertility celebrations. And some of it is just an irrational taste for pissing on other people's customs; one often recognizes these people by the fact that the insist so vehemently that this or that custom is really some other prior custom, even if it is quite clear that the current custom is not practiced as a continuation of the prior custom, based entirely on superficial resemblances. And, of course, there is an enjoyment in feeling oneself more knowing than the masses, even if the feeling is entirely founded on illusion.
So let's take the Christmas tree. Decoration of trees happens occasionally in various cultures. They are easy to decorate, so that's not surprising, and this fact does not actually help us to determine how Christmas trees originated. The earliest independent confirmations we have of actual Christmas trees are from the sixteenth century in Alsace and Bremen, but these are presented as if it is obvious what they were, which strongly suggests that it was not a new custom. Prior to this, we do have occasional references to the decoration of branches or boughs for Christmas, references that go back a few centuries further, and while some of these seem to have just been hung up by rope (like we do with mistletoe, but probably in a larger display). It's unclear whether this practice is really the precursor of Christmas trees, or Christmas wreaths (which is likely), or both. There are cultures that currently today display decorated branches in a fashion somewhat like the modern Christmas tree. The most commonly noted is the chichilaki, or St. Basil's Beard, a custom that grew up along the Black Sea. As far as I know, we don't actually know the origin of this practice, but it's not impossible that it goes back quite far. Current Georgians will often have both Christmas trees and chichilaki, so they don't see them as the same thing, but that doesn't eliminate the possibility that they may be two different branches of earlier bough-decorating customs.
Actually setting up trees for the holidays seems to have developed in Germany (like a lot of our modern Chrismas customs). Usually these seem to have been used as dancing poles or as the heart of a bonfire, but we know that in the sixteenth century they were sometimes decorated and sometimes were instead decorated with candies and fruits which were then given out to children. The practice seems to have become popular among Lutherans in some German towns and cities as an alternative to the nativity scenes popular among Catholics; for this reason, Catholics in German regions only slowly started setting up Christmas trees, since it was often seen as a Protestant custom. As it spread, however, Reformed Protestants also tended not to have them, seeing them as Lutheran thing. And, indeed, it was seen as a Lutheran practice by Lutherans, as well, which is perhaps why the legend sprang up that the Christmas tree (or sometimes Christmas tree lights) was invented by Martin Luther. The legend is hard to trace, as well, but it may have done some work later in a more ecumenical time by making it easy for non-Lutheran Protestants to accept it as a generic Protestant practice rather than (as it often originally seems to have been seen) as the Lutherans misdrawing the line between Christianity and Catholic paganism again.
It's usually thought that the custom started spreading in the Franco-Prussian war, in 1870, when one of the morale-building things done by the Prussian army was to set up Christmas trees for those of its soldiers who had the custom; thus a very large number of German men had their Christmas celebrations with a Christmas tree that year. In any case, the custom did spread in Germany. In Britain, Queen Charlotte (who was German) had occasionally set up a tree for Christmas parties; Queen Victoria had liked the trees so much that she had one every year, and the custom spread in Britain the way customs like wedding dresses spread -- middle-class and upper-class women imitating Victoria. The Christmas tree was spreading in the United States as a cultural practice among German immigrants, even those who did not come from regions in Germany that practiced it. This is a common phenomenon, in which highly distinctive and noticeable cultural traditions spread among immigrants even if it was not their practice in the homeland, like Scottish immigrants with tartan, as a sort of heritage-marker. Thus it was largely practiced in Pennsylvania and New York, and it's thought that it may have started spilling outside the German immigrant communities in part due to imitation of Queen Victoria again -- at least, wealthy Americans in areas that already had Germans putting up Christmas trees may have taken Victoria's tree as a sign that this was a respectable thing to do, and thus followed along. The practiced solidified and became universal in the twentieth century in the most American fashion possible -- department stores and businesses started putting them up. From the US it has been spreading throughout the world, as everything that ends up in American movies spreads throughout the world.
Ironically, the song most closely associated with Christmas trees -- "O Tannenbaum" -- which was written in 1824, had nothing whatsoever to do with Christmas trees or Christmas. It's an adaptation of an older folk song about an evergreen fir tree. As far as I know, we don't know the exact path by which it became associated with Christmas trees, but as the standard English translations eventually all started mistranslating 'Tannenbaum' as 'Christmas tree', the association was locked in.
In any case, unless you think dancing, or bonfires, or decorating branches are intrinsically pagan, there's no evidence whatsoever that any customs pertaining to the Christmas tree are of any pagan origin whatsoever. All our earliest evidence about any specific meaning it has associates it with Christmas. All our best evidence is that it's a late medieval or early modern practice, and it spread because it is a very distinctive and visually appealing practice and the ease with which it allowed guilds, businesses, and wealthy families to mark a celebratory season.
