By magic we don't mean actual magic because it really doesn't exist here—the only magical moments are his arrival and departure from Arthurian times. The rest of the time, it's a giant sham. Those who say they practice it are just con artists hustling the yokels (and sometimes themselves), specifically Merlin, who acts as the book's Big Bad Wolf (check out his analysis in the "Characters" section for more on this).
Conversely, those who believe in magic are either fools or crazy people… and there are a lot of fools and crazy people in this book. Even Sandy, whom Hank falls in love with, falls victim to it (again, hop on over to the "Characters" section for more on this).
Magic serves as a symbol for the fear and superstition of Arthurian times, the ignorance that Hank pounds against like a deranged bongo drummer for most of the book. Even he has to bow to magic's power if he wants to save his own life, starting almost immediately upon his arrival in the 6th century when he pretends the eclipse is magic. He works and works to remove magic's influence on the populace, struggling the whole way. He says,
I must keep my superstitions about unenchanted and unmiraculous locomotives, balloons, and telephones, to myself. (21.2)
He makes progress—slow, painful, pull-your-fingernails-out progress, but progress nonetheless. And then, just when he really seems to have pulled the country over to the side of disbelief, it all slips away. Like a lot of the other symbols in the book, it ultimately bites Hank in the end… undoing everything he's worked so hard for.