There are two types of magic:
The 64 spells (32 for each category) are divided into 8 levels of four spells each (per category). Each character had hold 3 spells of each level, so you will have to pick carefully. White and black Mages can use up to level 6 of their respective categories, and once they become wizards they can use any spell in that category. Red mages can use up to level 5 of either category, with some exceptions. Red wizards can use a many of the level 1 - 5 spells that Red Mages cannot, as well as a handful of level 6 and 7 spells. (See the "Red" Magic page for more on what spells to get for the Red Mage/Wizard).
 Dawn of Souls and the Anniversary Edition
In the original version of the game, characters could cast each level of spells a certain number of times. In essence you had 8 types of MP (one for each level) and each spell cost 1MP from their level's MP pool. In Dawn of Souls and the Anniversary Edition, you have the more modern style of MP where there is only one MP pool (for each character), and all spells draw from this pool. Different spells cost a different amount of MP.
In the original version, the effectiveness of magic was both highly erratic and bound to a certain range of HP lost/restored. For instance, Ice3 could do between 70 and 280 damage to an enemy. Unless the enemy was especially weak to ice, it would never to more than 280 damage to an enemy, regardless of the caster's level. Sometimes a single casting of the spell would do 70 damage to one enemy and 280 damage to the exact same type of enemy right next to it.
In Dawn of Souls, magic is determined by the caster's level, so as you go up in level, the power of the spell will increase. The effectiveness of a spell is much more consistent, so if a spell does 150 damage to an enemy, it will do about 150 damage against the same enemy the next time you cast it (assuming your level hasn't changed).