The books you probably want to read to find this out are the Genesis of Shannara series, which tells about the transition from "apocalyptic" Earth to "post-apocalyptic" Earth.
But, the basic idea is that magic had always been there, in the form of the Faerie creatures and their world. As humans began to flourish, the Faerie creatures removed themselves from the world, and mostly "took" magic with them. The magic dissipated as science started to take over. But, those magical elements were always there. Arborlon existed "hidden away" from man, keeping the Forbidding locked away behind the Ellcrys.
As told in the Word and Void series (which takes place about 100 years before the Genesis series), science eventually leads to nuclear war and the fall of civilization. Demons of the Void start walking the Earth trying to bring an end to humanity, and The Word (a source of good magic) calls humans to fight them. Eventually, as people begin to lose the knowledge of, and faith in, science, other magic starts to re-emerge. The Ellcrys tells the Elves that they need to go back out into the human world and find the Elfstones; magical creatures start being born again; humans begin learning to use the magic of "The Word", etc.
The rest of the story is told as these various factions "rediscover" magic, leading up to the first of the new Druids, etc.