Introduction
How not to do it
On one extreme end of the spectrum of possibilities stands the statement that magic is the opposite of science.
When science states that something is impossible, magic is the solution.
Everything is possible with magic!
You just will something to be and - hocus pocus - it will become reality.
The big disadvantage of this view is that it removes all barriers, all challenges, all creativity; in short, the gaming aspect of the game.
On the other end of the spectrum, magic is treated like a rigid system.
With spell X you can achieve effect Y, its magnitude determined by how many magic points you have.
If you want to achieve a more powerful effect, you need to get your character to level up.
All magic is cemented in these rote learning spells, which work in a very specific way, without being clear why.
With such a fixed set of rules, creativity and fun are not removed but hemmed in so much that they are effectively annihilated also.
Magical science
So, if the extremes are no fun, how to do better?
In my opinion you should start by the basic premise that magic is the art of bending reality.
Science, observation, common sense and tradition have a firm grip on reality, but not an absolute one.
Everybody knows that an aeroplane can fly, but how many of you really know how flight works?
For the minority who do, it is all very clear, but for many people flight really is quite magical.
Once in the realm of magic, alternatives become possible.
Suppose that a human can fly by strapping wings onto his or her arms and flapping, like a bird does.
Scientific mainstream claims that it is just not possible and can prove and explain it too,
but as long as that proof and theory are not solid, how can you be sure that human birds cannot be?
The key to a magical system is to push back the frontier of science, to a point where many things are not properly understood and proven.
In such an environment, alternative explanations are not yet ruled out.
The key to a magical system is to make these alternative theories reality in the game.
Alternative magical theories tend to be the most fun when they warp, twist and stretch the modern scientific mainstream, but not too much.
After all, magic is about what people believe is true, not what actually is, yet they will not believe utter nonsense.
Who will accept that you can resurrect a dead deer into two and a half purple mice, by waving an exactly week-old mushroom in front of it while shouting "Khazam"?
But allowing people to fly by flapping magically constructed artificial wings, partially transforming into birds, or commanding the wind to lift them up ...
Those might be acceptable explanations in a magical world.
By allowing the magic system to introduce 'fantasy science', without slipping too far to the 'anything is possible' extreme, you can create very interesting gameplay.
Magic itself can become something to explore and experiment with.
Let me show this by a quadruple example.
Example: invisibility
This example is about a well desired feat of magic: the ability to become invisible. Lately there have been some examples of advanced technology that achieves partial invisibility, but this phenomenon is still almost completely in the domains of science fiction and fantasy. I will describe not one, not two, not even three, but four ways of achieving it through magic, if only to show that magic should not be confined too much. Maybe you can think up a fifth, sixth, or more yourself!
Physical invisibility 1
This magical theory says the light is a physical substance which shares some attributes with liquids and fluids.
Like those, it can flow around hard obstacles.
It does not normally do so, because it flows too fast.
But a mage can slow it down, so much that the flow characteristics reappear.
Thus, he or she can make light flow around people and objects, instead of reflecting off them and so make them invisible.
This kind of invisibility does have some side effects.
Light that is slowed down reaches an observer later than light that passes the invisible thing at full speed.
In a scene where the background is not static but changing, this will create a distortion in the view, allowing an observer to spot the outline of the invisible area,
so that it is not completely invisible.
You can also surmise that slowed down light is absorbed more than light at full speed, warming up the invisible thing, so it cannot be kept up for too long.
Physical invisibility 2
This magical theory operates from the dogma that everything is made up from four elements: earth, water, air and fire.
That's a well known theory that has its roots in some of the murkier areas of ancient Greek philosophy.
I proceed to state that light is a form of fire, which can pass through other elements, but not in equal proportions.
It passes through air without trouble, through water with some distortion and through earth not at all.
Many physical objects are a mix of several elements and so are our bodies.
The earth and to a lesser degree the water in our bodies blocks light, absorbing and reflecting it, thus making us visible.
So, in order to become invisible, one must get rid of the earth (and water) and become more air-like, so that the light can pass through.
With proper elemental transmutation magic, which I will not detail here, this can be achieved.
In this theory, invisibility has interesting side effects.
A person who is well invisible must be quite airy and therefore will also be very light.
On the positive side, he or she may be able to walk over quicksand or even water and physical attacks may have very limited effect on him or her.
On the other hand, heavy winds may whisk him or her away.
No doubt you can think of other effects.
When applied during roleplay, this kind of invisibility creates all kinds of advantages and disadvantages that need to be tackled - a true gaming experience!
Sun, Moon and Stars
The Sun, Moon and Stars theory claims that there are three forms of light: sunlight, moonlight and starlight.
The notion that moonlight is just sunlight reflected by the Moon is nonsense; the Moon itself radiates light, but of a different kind than the Sun.
Stars shine a third kind of light.
These lightforms have different attributes.
Sunlight is brighter than Moonlight, which is in turn brighter than Starlight.
Sunlight has colors, others do not.
Some objects are visible in all three kinds of light, others only in two or only one.
To become invisible, a mage has to assume Sun-, Moon- or Star-nature.
For example a Moon-mage is invisible in Sunlight or Starlight.
This theory calls up questions and can be expanded to include much more than just light.
Maybe there exist Mooncolors and Starcolors too, but of a different kind than Suncolors.
What if Moon-visibility comes with other Moon-related phenomena, like lycanthropy?
Possibly a Star-clad mage cannot eat vegetarian food anymore, which after all is based on plants that grow in sunlight.
And the list goes on ...
Mental invisibility
The mental theory states that all the physical explanations are sheer rubbish.
Invisibility is about not being seen and seeing is part of perception.
There are numerous of examples of people not seeing things that are right in front of them, because their attention is focused elsewhere.
So the key to invisibility is distracting them.
A good illusionist can do that with shadows, gestures and creating striking effects,
but a real mage telepathically projects those distractions right into other people's minds - again a process that I will not explain here.
This theory has different consequences than the previous one.
Because it is all about perception, invisibility does not need to apply to sight only, but can also encompass hearing, smell, touch or other senses.
But the mage can only influence people who he or she is aware of.
People that are unknown to him or her, through their own invisibility, hiding in shadows or just creeping up on the mage from behind, will be unaffected.
Animals that are too stupid to be distracted by the mental imagery will be untouched also.
Again you can think of other side effects yourself.
Conclusion
Hopefully it has become clear that magic can be much more than 'hocus pocus poof!' or 'cast spell X at the target for Y magic points'. If set up well, it can be a rich environment that has many connections with the roleplay. If as a gamemaster you want tight control, you can flesh out magical systems and subsystems yourself, carefully balance them with the rest of the game rules and then use them in your games. If you are comfortable with more freedom and experimentation, you may even allow your players to invent magic 'theories' of their own. After all, wizards are supposed to be intelligent and creative!