I could run magic through the system without needing to make any real changes at all. It could fundamentally work like any other part of the game. In this way, a group would...
1. Determine what traits might give an advantage (as defined by the current narrative situation).
2. Roll the three dice and determine the way the traits modify the outcome.
3. Apply new positive and negative traits as determined by the result of the dice.
4. Continue on with the story.
But that's basically like saying a "Powered by the Apocalypse" game can simple be reduced to...
1. Choose the attribute most applicable to the task at hand, and pick three positive outcomes (where the absence of a positive implies the presence of the outcome's negative).
2. Roll 2d6 and apply attribute modifier.
10+: All three positive outcomes come true.
7-9: Either two of the three conditions come true, and the third condition invokes an inverse effect that complicates the story in some way...or, one of the three conditions comes true, and the others are basically ignored.
6 or less: None of it comes true, and the pain comes down.
3. Continue on with the story.
It's an oversimplification that could easily be applied to any "Fate" powered game just as easily, and as a cold, reductionist description of play mechanisms, it really doesn't do a lot for any of the games to be described in such a manner. The other half of the equation is the story, but that can be pretty loose and freeform (or very linear, depending on the GM and the group's play style). It's the interface where things get interesting, the nebulous relationship between mechanisms and story.
+Ron Edwards writes some great posts, and a few months ago he wrote one on the powers within the game "Champions" (actually, he writes about this game reasonably often; but there's one particular post that I'm thinking of). In that particular post he described the way powers could be bought as a range of abilities (which could be mixed and matched on the fly to create the effects of a hero...even the vague Schroedinger's box of "Batman's Utility Belt"), or powers could be bought as specific effects. I vaguely remember the post describing the way certain effects were limited by the current narrative, this was reinforced by a more recent post (this week I think) where power costs could be bought down by applying certain penalties to them (where such penalties would have instant narrative potential).
That's basically where I'm going with this magic, but making sure it seamlessly integrates with the rest of the system, ensuring it is informed by the same design methodologies that created the game in the first place, and yet the addition to the game must add something new and beneficial to the mix.
Magic(k) with a "k" brings concepts like paradox, Arete, vulgar and coincidental effects, spheres, and quintessence. Pretty much everything else is dressing to help a player manipulate those fundamental concepts.
But what does magic(k) actually do. In the narrative, it has the potential to do literally anything; it can take almost any appearance but some appearances are harder to achieve than others (hence the coincidental/vulgar divide). In the mechanisms, it has a basic spectrum of effects...completely stop progress along a specific avenue...impede progress along a certain avenue...accelerate progress along a certain avenue...completely skip parts of the avenue to get ahead in the story. At the crudest level, the same could be said about anything in any RPG. Combat might be improved by certain mechanisms or impeded...the wider mechanism of combat itself might improve or impede the grander story. (Here's where I think a lot of players don't like the "railroad" style of GMing, where protagonist actions that should change the narrative have no effect, thus deprotagonising the "heroes" and finding things simply directed back to their course...but that's another rant entirely).
But let's focus on the Magic(k).
Arete determines how good you are at fundamentally changing the course of the narrative, type of sphere constrains the type of manipulation from a narrative perspective, level of sphere determines how proficient you are with a specific narrative blend of magic(k), quintessence empowers the effect (making it easier to manipulate the narrative), and paradox basically applies complications to the ongoing story.
Paradox is easy in a FUBAR. We have tokens that move back and forth as the story progresses. Paradox could simply move tokens against the flow, new things to overcome as reality gets in a character's way (it might be possible to have personal paradox that simply increases the difficulty or complicates actions for a single character, or communal paradox that affects everyone, but conversely may be addressed by anyone).
Quintessence is also a fairly easy fit, because it links in with Paradox (through the "Quintessence Track") and because it exists in game as a pool of expendible points. Since we've already got pools of tokens, adding another variety of interactive token doesn't bend things too much. FUBAR has already experimented with single use traits (in one case allowing rerolls, in another case expending a trait allowed a new trait to manifest as a part of the action). I've seen these work, so there's no real new ground covered here.
Spheres and Arete, they get a bit more tricky. Both of these work on scales (Arete 1-10, Spheres 1-5), while FUBAR works with a two level scale (basic/advanced). For a Mage hack, I'd be inclined to use the longer scales, for a standard FUBAR system I'd be inclined to use the two levels (I'd also shift the spheres, in order to make a distinct mysticism for the game).
But more on that with the next post...