Magic is basically a natural law in the worlds of fantasy, much like gravity or thermodynamics. Instead of scientists, these worlds are populated with old guys sporting white beards, pointy hats, and a penchant for fast-pitching fireballs, assuming they can pass their ability check with a d20 of course.
What makes A Song of Ice and Fire so refreshing is that there are no traditional wizards, and magic is not handled in the traditional fantasy way either. There are old guys in robes called maesters, but they act more like old-timey scientists and doctors than magicians. And while magic is present and accounted for, it's a very elusive phenomenon believed by many to be either tale or ancient history.
Abracadabra (But Missing the Alakazam)
If we had to summarize magic's symbolism in a sentence, we'd say magic represents the supernatural in A Clash of Kings. We know that's not a mind-blowing statement, but when you consider how Martin handles the material, especially given its typical use as a fantasy trope, then that statement becomes a little more nuanced. For example, there are several instances of magic in A Clash of Kings, but many of these contain hints that they are simply tricks or illusions.
When Stannis grasps Lightbringer from the burning effigy of the Mother, he supposedly has drawn a magical sword sent to him by his god to defeat their enemies—and yet his glove begins "to smolder" and he quickly "thrust[s] the point of the sword into the damp earth and beat[s] out the flames against his leg" (11.Davos.21). Hardly the image of might and majesty one would expect from a god granting his power to a mortal, right? Feels more like a stage performance gone wrong.
And in case the reader has any lingering doubts that the sword might be the read deal, Salladhor Saan tells Davos that the sword is certainly not Lightbringer. He argues it is merely a "burnt sword" (11.Davos.65), since true magic comes at a far greater price.
Varys's history suggests another instance of maybe magic, this one a bit trickier. After being sold to a mysterious man, Varys was castrated as part of a Blood Magic ritual. The man burned Varys's, um, manhood in the fireplace, and Varys heard a voice emanating from the flames. As he tells Tyrion, "Was it a god, a demon, some conjurer's trick? I could not tell you, and I know all the tricks" (45.Tyrion.128). The eunuch admits he had been drugged and was in pain, but the voice still haunts him—Varys cannot be sure of the reality of his experience, and neither can we.
Finally, there are characters who flat-out do not believe in magic, such as Maester Luwin. Sharing his opinion on the subject, Luwin tells Bran:
"Perhaps magic was once a mighty force in the world, but no longer. What little remains is no more than the wisp of smoke that lingers in the air after a great fire has burned out, and even that is fading. Valyria was the last ember, and Valyria is gone. The dragons are no more, the giants are dead, the children of the forest forgotten with all their lore." (29.Bran.107)
Despite living in a fantasy novel—okay, to be fair, he isn't aware he lives in a fantasy novel—Luwin considers the word magic to be a "want for a better word" for a "different sort of knowledge" (29.Bran.95). This knowledge, whatever it was, is mysterious only because it is lost in history, vanishing from the world when the children and dragons died out.
We don't think it's a stretch to say that, from Luwin's viewpoint, magic would be just like any other knowledge had it stuck around. In other words, it could be studied, catalogued, and then filed away under Not Really That Mysterious After All.
In many ways, this adds a sense of reality to the fantasy. Even in the 21st century, debates occur between people who claim only natural laws govern universe and those who believe supernatural forces influence our world and humanity's path in history—consider this debate between Bill Nye and David Ham on the subject of evolution and creationism as a contemporary example. Many of these debates center on the same themes as Luwin's speech above—that is, knowledge from the past and its value, as compared to the knowledge of the present.
Likewise, modern people often claim to have paranormal experiences, from UFO abductions to encounters with angels, haunted houses to near-death visits to heaven. Others argue these encounters have purely physical explanations, like neurology, or can be explained as good old-fashioned trickery. As you might have noticed, Varys's story is basically a paranormal experience with Tyrion playing the skeptic.
So we end up with a reading experience in which we can't be certain whether magic is real or imaginary, natural or supernatural. And in many ways, the book reads more like a discussion about the supernatural, rather than just assuming magic is a given simply because the book is of the fantasy genre.
Dragons with the Assist
In A Clash of Kings, magic seems to be making a comeback, topping the Westeros charts as a number one hit—only this hit is of the assassination variety.
The shadow assassins Melisandre births to kill Renly and Ser Penrose certainly seem supernatural, although we can't say much about them other than they get the job done. Likewise, Bran's skinchanging abilities are also magical, and we learn from Jon's adventures beyond the Wall that certain wildlings, called wargs, have had this power for quite some time now.
The source and extent of magic's return is hidden by the novel's end, but there are hints connecting it with the return of another fantasy trope: dragons. While discussing the creation of wildfire, Hallyne notes to Tyrion that the production of wildfire was sped up thanks to certain spells becoming more effective. He remembers a time when another pyromancer told him that magic "began to go out of the world the day the last dragon died" (50.Tyrion.56). Dragons have certainly returned to the world; does this mean magic will, too?
We bring this up to point out that magic's symbolic nature might change in later books of the series as we receive more information about it. A Game of Thrones has next to no discussion on magic, but A Clash of Kings has significantly more. A Storm of Swords could provide answers for this mysterious phenomenon or leave us with more questions—only time and further reading will tell what kind of symbolic role magic will play in the series A Song of Ice and Fire as a whole.