Figured I'd throw in my two cents because it's rare to find a developer that gives a damn:
I am very much in favor of a game world being believable--ie, explainable--in as many instances as possible. Why? Because if the game says "Oh, it's magic. That's just the way it is," that's a little more of my brain that didn't get to investigate and learn about the fictional world it's exploring. And thus, I care a little less about the game world. In short, use of 'cop out' answers or explanations like 'magic' leads the gamer away from thinking, and the less thought the gamer does, the less he cares about the game.
Thus, I propose the following for your dealings with 'magic' in the gameworld:
'Magic,' pre-fall, could be an energy source leaps and bounds beyond any other energy source found in the world at the game date. It could be like the Romans discovered nuclear energy (not the details of it, just the application) long before gunpower was even close to being tripped over and discovered (at least, historically). Alchemists who toyed with mysterious chunks of ore that glowed softly in the dark discovered a heavenly power within, for example.
Of course, actually using nuclear reactions as 'magic' would be a little, uh, cliched. Your game already looks enough like Fallout. :wink:
Maybe the Romans came upon a kind of energy we can only hypothesize about today? Like, an energy application of String Theory, or Antimatter, or Dark Energy, or something? Just because it's not scientific fact doesn't mean you can't explain and build a mythos behind it -- look at Alpha Centauri, for instance! That game's tech tree was sheer brilliance, because it paired real science with fictional expounding.
Hell, if you want your work to be easy, go find a crackpot article on Anitmatter/Dark Energy/String Theory and just, well, copy it wholesale as your definition for 'magic.' Really, anything making claims about understanding any of the above at this point is going to be crackpot, and will likely turn out to be 99% wrong, but who cares? Such things are fantasy even in modern terms, and probably will remain so for the rest of our lifespans.
In short, when I'm exploring the ruined 'magical' laboratories in your game, I don't want to find some abstraction like 'MAGICAL ORB' and then be told, oh, this is what destroyed the old world, it's suuuuuuuper deadly. I want to find evidence of this 'magic' being the interaction of natural forces. I want to dig through the remains and the dust and, as a player, say "Holy shit, this wasn't some abstraction, this is an alternate earth after all."
It's the 'Planet of the Apes' effect. It's coming to a strange new planet after years upon years of cryogenic sleep/space travel, getting captured by the native ape creatures, having an adventure and making a daring escape, and while you're running away in the final scene, coming upon the fucking head of the Statue of Liberty half-sunk on the beach. Holy fuck. This is Earth.