Here are my thoughts.
I don't know if it's necessary to decide which side the PCs will ultimately end up on -- you could try planning it for both ways. Make it a factional thing; you already have the BigBadEvilEmpire, which forms the 'rebels' out of necessity. Maybe throw in a third party which has it's own agenda, or maybe something as disinterested and agenda-less as a druidic circle which doesn't care if BBEE is taking over the place. Or, whatever factions you come up with.
Then, flesh them out a bit, not too-too much, but have a grasp at why the higher-ups are doing what they are doing. Controlling magic would seem to be based on trying to maintain power and fear (both of losing power and of magic itself). Maybe consider having the BBEE be lower magic then areas outside it's control - the PC's are a group of people trusted enough (for some reason) to wield magic in defense of the realm. You could also treat it in an almost Dark Sun light; maybe Magic, for one reason or another, is having very negative effects on the world, but many don't know or don't care. Or, even yet, Magic isn't havign this effect, but the leaders of BBEE think it does.
What does the BBEE want? What do the rebels want? (Will the rebels be any better than the empire?)
When you start getting ideas together, come up with a basic web of connections between people in the different groups. I recently started reading this thread
t.r.a.p. and the way he goes about putting events together fascinates me. I haven't had the time to give it a go, but it could spark something. Have a mutable world that the PCs can interact with, can grow, and can ultimately decide what will happen.
Ideas for adventures, most of which are fairly cliché. This is mostly going to be ramblings.
Scout/raid an enemies magical storehouse.
Find the double-agent.
Prisoner exchange/hostage situation.
Getting another faction to support the PCs.
Covertly forcing/framing a faction to join the opposing side.
Put down a peasant uprising.
Start an uprising (so the BBEE has reason to send troops into an area).
Public-Image work
A McCarthian 'purge' of higher ranking members.
A suicide mission - when they are no longer useful.
Other things to help with the theme:
Situations where the party has to choose between two goals, e.x. Ordered to arrest/kill someone they know and respect
Having to choose between orders and their own values (house burning down, an illegal magic user casts a spell to put it out - they were on scene to witness the 'crime' and have been tasked with putting the criminal to justice)
Lastly, anything that would fit in 1984 or Fahrenheit 451 should work rather nicely. Also, Equilibrium; gun-kata fighting priests in a dystopian world.
Edit:
I forgot two points I wanted to mention.
1) Have a lose time line so that the PCs are near plenty of action. Maybe there's a 'planar conjunct' or similar pseudo-mystical technobabble which will ensure BBEE's conquest of the world. Everyone who is out to end the tyranny is kicking into high gear. Maybe, if Magic = dangerous, the world is at a 'mystical tipping point', so the BBEE feels it has to stamp out magic now. Or, the Death-Star is about to be fully operational, so the rebels need to hall-ass to Endor. The conclusion should be big.
2) I don't know if the PCs need to make a collective choice about what side to join. As long as they are never given missions to kill each other (Paranoia is such a fun game), they could manage to work separately for different sides. An enemy agent is not going to announce his allegiance to anyone who comes by. A PC who is fully indoctrinated might not automatically kill his co-worker, when he might be able to infiltrate the enemies society.
There. I think I've said everything I wanted to.