Cecil blew part of the answer while remarking about Victorian Christmases in: http://www.straightdope.com/classics/a3_014.html
He stated that Christmas trees are of German origin, but in fact the bringing in of a green tree is of Pagan origin, and is not country-specific.
GonnaWin
In this column, Cecil merely states: “Other contributors to the Victorian Christmas tradition include Prince Albert, husband of Victoria, who popularized the Christmas tree, previously a German custom.” (Prince Albert was German). Cecil never said the practice originated in Germany, only that it was a popular custom there at the time, which no one disagrees with.
While I’m here, I might as well point out that this column appears on page 14 of Return of the Straight Dope. Unfortunately, it doesn’t have a Slug illustration. Fortunately, the book contains many other Slug illustrations, not available online, which makes it a bargain at even ten times its price.
You might want to note that there is no such religion or tradition as “Pagan.” There are pre-Christian religious traditions of various countries and regions, some of which survived, in various forms, longer than others. But there is no such thing as “the Pagan religion.” (Odin is not the same as Jupiter, for example.) So any tradition would have a specific geographical origin (unless you are claiming that all pre-Christian peoples, from Norway to Zimbabwe and Maine to Australia, brought in fir trees to celebrate the winter solstice. If you claim that, you’ll have an interesting experience on this board, to say the least.)
An excellent reference on the origin of Christmas Trees is Nussenzweig’s “The Battle for Christmas”. A real eye-opener, and it dispels a lot of untruths that have gathered around this topic.
When I was in Catholic School they taught us that St. Boniface was responsible for the practice. I haven’t heard that one anywhere since.
You might want to note that although there is no historical religion “Pagan”, there are quite a few modern adherents who would consider it a religion.
The alt.pagan FAQ ( http://www.landfield.com/faqs/paganism-faq/ ) discusses this more in detail.
Of course, the modern adherents aren’t the ones who started the tradition of festive conifers, either.
While I firmly believe in people’s right to call themselves whatever silly thing they want, referring to one’s own religion as “Pagan” makes about as much sense to me as starting The First Heretical Church. Or perhaps forming the new state, Barbarian-land.
But I am a well-known cynic, so my views may not be widely held…
G.B.H. Hornswoggler, if you are thinking that a “pagan religion” is a paradox or self-contradicting statement, I would have to disagree. “Pagan” can mean, according to my small desk dictionary, one who is not a christian, moslem, or jew. Therefore a person who worships the spirits of the woods could very well belong to a pagan religion.
“The First Heretical Church” is a better example.
Which reminds me, have I ever mentioned here the two scholarly treatises I have written: “Nomadic Urban Planning” and “The Grammar of Solecisms”. 
Animism is actually the most widespread religion. From Inuits to Hottentots to Maoris.
Etymologically, “pagan” means, more or less, “hick”. So do “gentile”, “goy”, and “heathen”. In practice, it has several meanings:
Not Christian or Jewish. (Historical use only.)
Not Christian, Jewish, Moslem, or spin-off (Mormon, Jehovah’s Witnesses, Mandaean…), and, obviously, not Atheist, etc.
Not any of the above; also not Buddhist, Taoist, Shintoist, or other “respectable” religion.
Polytheist (i.e., same as 3, but also excluding animism and modern fakery like Scientology).
Wicca, or a spinoff, or the “anything-but-Christian” crowd in general (and since they typically have no more notion of Christianity than the average pro-wrestling fan has of Shakespeare, that “anything but” covers a wide range).