Pagan basically means "country dweller," and it got its connotation because the "country" folk, the non-urbane, less "civilized" people, were among the last to have the modern religion--in many cases Christianity--brought to them. In the past, everyone was a "country dweller," and at the dawn of human history people worshipped and gave reverence to natural phenomena, glorifying it as the direct cause of their existence. There was mystery surrounding life and death, the Earth's cycles, and many life processes that have now been studied by science. People's desire to control their environment and to appease whatever forces might be causing their fortune (and misfortune) gave rise to primitive religions.
It was easy to draw the parallel between the Earth's giving birth to the harvest and a woman giving birth to children, so in early times the Earth was personified by a Goddess figure in many places, with most places also giving Her a mate, a God, who would come to fertilize Her and to father His own future self, much as the Earth is continually fertilized by its own bounty to give rise to more of the bounty. As is the way of humans, the primitive peoples gave myths and stories and personalities to their ideas of God and Goddess, in places all over the world coming up with deities that resembled themselves. Warlike Gods and Goddesses sprung up among warrior people, deities of the hunt arose for nomadic hunting tribes, and as humanity became more settled and agrarian for the most part, deities for farming, plant fertility, and family were created.
It should be understood that these gods and goddesses were believed in as strongly as many people believe in their gods today. They did not think of these as myths and stories, any more than most Christians consider the birth of Jesus and His saving of mankind to be nothing but a parable story. This was no big game, or an excuse to have harvest parties, or just something to do. The people lived close to the land, and felt it to be alive, and wanted its approval. So they created rituals that they believed helped manipulate their situations; they gave gifts and sacrifices to the gods (usually in the form of the best part of the harvest or some of their livestock being ceremonially given to God, but if you go back far enough there is always some more brutal sacrifice in man's history).
In most settlements, tribes, and villages there were special people who had gifts for healing, knowledge of herbs, and were thought very wise. Many of them were women, because they were often midwives and very compassionate healers who cared for the sick, but there were plenty of "medicine men," so to speak, and a select few learned these arts. But usually in olden times everyone celebrated seasonal rituals and marked their days by the waxing and waning of the moon, and all acknowledged the power and knowledge of the village shamans, healers, witches, whatever they were called. It was just like having a chief or a president, or pointing out the clan's best hunter, or having every man after the most beautiful girl. People's gifts were acknowledged and in some cases desired, but not usually feared like they came to be in later times.
It is mainly unknown how much of ancient Witchcraft still survives. Some people in family traditions claim to be able to trace their "witch" lineage, handed down through the generations, back very far. But, considering how little it is possible to document from such ages past, it is hard to tell how much what we practice today is truly like the rituals of the past. The point is, most of history points to our ancestors having seasonal rituals and practicing mysterious rites as an attempt to control their environment. Much of it was probably superstition, such as the plethora of omens from all over the world, but quite a lot of stock was put in it, and people were often more superstitious in the past because so much was not yet understood by science. But even today, few people have lived their lives without trusting in a lucky charm or following hunches based on nothing rational, so when that is taken into account, it is easy to understand why people of the past believed their rituals worked. Experimentation, insight, and various forms of herbalism gave rise to practices of magick, some of which survived right up to modern times.
So, back to tracing the history: As mentioned, some people believe they can trace family heritage of their traditions back to ancient times or before the Middle Ages, but very little is documented before a few hundred years ago. A new religion, Christianity, began to spread, with its leaders determined to convert and conquer, for the "enemy's" own good. They met with quite a bit of opposition, because people didn't want to stop practicing what they'd always practiced; remember, they believed in their gods and the importance of their rituals as strongly as the Christians believed acceptance of Jesus was necessary or the alternative was burning in Hell. Wars were fought, but the Church was in power, and made short work of many Pagans before they were through. A Pope declared the Inquisition and made it actually illegal to practice the Old Ways. Some of what the Christian leaders did was for political reasons, but overall the whole point was that they were trying to save everyone. (Killing them in wars and burning them as Witches was not the most compassionate way to do it, but people are imperfect, and hearts were kind of in the right place. When Christianity first arose, after all, the Roman Pagans tried to feed the Christians to the lions, so it happened on both sides.)
The Christian church decided the best way to convert the Pagans was to redirect their old rituals to their new purpose. They tried many ways to do so, and many of them were successful. Over several hundred years, new holidays were created and old holidays were renamed, with meaning reassigned and symbolism incorporated. That is part of the reason the Christian Easter still bears the Pagan fertility symbol of the vernal equinox (the egg), and why many still decorate it in the same way our ancestors did. That is part of the reason Christmas was celebrated as Jesus's birth to make it correspond with the winter solstice, the day the new Sun God is born of the Goddess in many Celtic and European Pagan traditions--even though in the Bible there is quite a bit of evidence that Jesus could not have been born in the dark of winter. The Christians made a serious and conscious effort to make the Pagans change the direction of their rituals instead of the rituals themselves, making them more comfortable since they were taught to think it was all the same thing anyway, and ultimately they were successful. Christmas songs still bear the word "Yule" in the Pagan way; Christians decorate Pagan symbols of the God with fairly un-Christian five-pointed stars; Christians give gifts in the spirit of our Pagan traditions.
Witch-burnings, persecution, fear, and general ignorance pushed all forms of Paganism underground for a long time. Those who still practiced did so in secret, but it was so tough to pass on the knowledge even to one's own descendants (for fear of being ratted out) that a lot of the rituals, practices, and knowledge were lost. People valued their traditions, but they also valued their lives, and a candle can only light the way in the dark for so long. The Old Ways were largely forgotten, especially for groups such as the Druids, who kept no written records. The British Isles were affected less strongly by Witch persecution than most of Europe and the New World, and some traditions did survive there even though the government did have anti-Witchcraft laws on the books. It was dangerous to be open about it, but it was also well-known that people were practicing and had been for some time, especially out in the country where some settlements were barely touched by the whole ordeal. In the New World, Native Americans practiced forms of religion that were shockingly similar to some forms of European Paganism (i.e., they respected the Earth, practiced herbalism, gave very deep religious symbolism to objects, et cetera, though they were not some peace-loving utopian society like some people try to make "Indians" out to be). These "savages" were also pushed to convert by the colonists, and many signed treaties allowing white men to stay on their land, not understanding that they were agreeing to ownership of the land, since they did not quite think of territory the same way. Their religions were also all but stamped out.
Over the next few centuries, societies grew and changed, and more of the old ways were pushed into obscurity. Some flarings of Witch persecution arose from time to time (i.e., the Salem Witch trials and various crusades), but it stopped being such a danger to those in power anymore since everyone who wasn't Christian at least appeared to be on the outside. Various Pagan religions and magick-working practices survived under the guise of fiction, or in preserved family books, or in oral secret traditions kept by families or groups of families, who'd gotten quite good at hiding by now if in fact they were existing under the nose of the modern public.
It's important to remember, by the way, that the Salem Witch Trials and all the other reported Witch persecution was mostly NOT in response to actual Witchcraft. Many Pagans of today like to cite these dark days as something never to be forgotten in the name of freedom of religion, but many of them also fail to understand that these people weren't actually killed for being Witches. They were killed for various reasons; either they were actually suspected of being Witches but were honestly Christians, or they were in the wrong place at the wrong time, or they happened to be unlucky enough to have a Witchfinder point a finger at them. (Greed, paranoia, persecution, and hysteria are all very distorting lenses to look through, and anyone with such colored glasses is bound to see a pointed hat on a bare-headed person.) It is unlikely that there was much Witchcraft going on in secret at all at this point, except for isolated family traditions that were mostly superstitions and light rituals and collections of tales. In any case, the small clumps of Earth-oriented "Pagan" beliefs look very little like the Wicca and prescribed traditions of today. Let's go into that.
Now we come to more modern times--the rise of Gerald Gardner. He was an Englishman who is oftentimes credited with the current popularity of Witchcraft and Wicca. In the early twentieth century, Gardner received some sort of initiation from a woman referred to as Old Dorothy, who probably practiced some sort of unique family tradition. He began gathering information to bring Wicca, as he called it after the word wicce (most say it means "wise," though there's plenty of debate about that too), back to the public eye. He took what he learned from Old Dorothy and also researched what literature there was on Witchcraft and the occult. He incorporated quite a bit of information from Aleister Crowley's dark publishings, and also paid quite a bit of attention to the work of Leland, who published some information on some Italian Witchcraft practiced by gypsies, with legends and stories about the descent of Aradia, who was later interpreted as a Goddess or "the" Goddess. He began forming somewhat underground groups and was aided by Doreen Valiente, who reorganized his notes and helped him throw out some of the things that didn't belong (i.e., things from Crowley that sounded like Satanism, et cetera).
Gardner started some covens and began to spread Witchcraft, in his form, all over Britain. His form of Wicca began to be referred to as Gardnerian Wicca, and in modern times Gardnerian Wicca is about as "traditional" as you can get when you're practicing a Pagan religion. It is very ritualistic and the initiation process has lots of rules; every Gardnerian is supposed to be able to trace his or her lineage of initiation directly back to Gerald Gardner himself. Also they are generally made to copy "the" Book of Shadows Gardner made, by hand, for many reasons. There are three degrees of initiation in Gardnerian Wicca, and the rituals are generally done in the nude, with very prescribed rituals run by a priest and a priestess, and they're very centered on working partners, on balancing the male and female polarity.
A man named Alex Sanders was taught in the Gardnerian way and disagreed on some points, and reinvented the religion for his purposes. Alexandrian Wicca, as it's called, is also quite traditional but has some differences in initiation and a few more things. Sanders's pupils, notably a pair of working partners named Janet and Stewart Farrar, became prolific writers and helped spread knowledge of the new brand of Paganism. Gardner and Valiente both had influential writings too, some of which had been published as fiction before Witchcraft laws were repealed in Britian, and the interest grew. Different sects broke out, and others were reinvented or brought back from the dead. There are now practicing Druids again (though perhaps very few on Earth know how similar their rites are to the ones of old); there are Dianic Wiccans who emphasize the Goddess and give honor to the God only as Her Consort in one phase of Her life; there are Green Witches and Kitchen Witches and Garden Witches who mostly apply the religious principles of Paganism to everyday living and attach little mysticism to it; there are Faery or Feri Wiccans who practice a form derived from the Celtic folk customs and ceremonies; there are forms of Native American, shamanistic, tribal, and local traditions that have been revived; and most notably, there has been a very big increase in eclectic practice (i.e., practices that just incorporate whatever is thought "right" by many traditions), especially by solitary Wiccans, Witches, and Pagans.
There is some controversy now over what Wicca, Witchcraft, and Paganism are. By definition, you are Pagan if you practice something that does not worship a monotheistic God. But in the more accepted definition, Pagans celebrate some sort of Earth religion that gives reverence to the Earth and takes notice of its cycles. Magick is a difficult practice to define, but it is considered a practice, and though it is rarely practiced independently of a belief system that is Pagan, it is possible; therefore, it does not mean you're Pagan if you happen to practice magick, nor do all Pagans practice it. Most Witches and Wiccans do, though, if only by making simple charms. Most people who consider themselves Wiccans either believe in a certain set of rules and do their rituals a certain way, or else they practice with a Wiccan coven and have been initiated as Wiccans. (Some Wiccans say that solitary Wicca is impossible because it was not created to be practiced alone, but that idea has been challenged plenty, most notably by prolific Wiccan writer Scott Cunningham, who has several books on solitary Wicca.)
In any case, some people maintain that the current forms of Wicca, Witchcraft, and Paganism have survived through the long years, mostly unchanged, to be gloriously celebrated in this time of freedom. Others insist that it was more or less created by Gerald Gardner as recently as the early twentieth century. My personal opinion is that it was a mix of the two. Gardner helped bring it into the public eye, but there are accounts that prove it was flourishing in some form--and had been for quite a time--before then; accounts such as Charles Leland's experiences with the Italian gypsies in the eighteen-hundreds, and Rhiannon Ryall's description in her book West Country Wicca of growing up in the old country with old rituals similar--but not identical--to today's modern Wicca. Paganism wouldn't have become as popular if someone like Gardner hadn't made it a "crusade" to bring it back to the world, but the Craft has existed in some form all over the world since the dawn of consciousness; artifacts, writings, and family traditions prove that, not to mention that the Witch Trials weren't in response to something that was totally imagined.
So now, people are embracing Paganism in order to be more of an active participant in their religion; to see nature as holy; to connect with their past; to affirm the feminine half of life instead of insisting God is strictly male; to center themselves with the seasons; to align themselves with the moon; to try to establish control over their destiny; to find something that works. And whatever form of Paganism these people are choosing, it is undeniable that the movement itself is still growing and changing, taking its participants along for the ride. We, collectively, are history in the making.