It's tough to give a good suggestion without a better idea of the game as a whole, target audience, etc. Is everyone in the game a mage learning spells, or is this just one possible class? Is this an MMO or a single-player RPG? Is it action-focused or more turn-based combat?

If you want the most control over when and how a player gains new spells, I'd definitely add some unique resource (Research Points or whatnot) that they need. Then you can give players Research Points naturally as they kill enemies, add some mini-game where they can earn them, or just let them buy them (so different player types can unlock according to their play-style).

If this is an action-RPG like Magicka, the self-exploration would probably best compliment the game. When casting is quick and fun it's cool to experiment. But if this is a turn-based thing it could grow tedious trying out a bunch of combinations, and then accidentally killing the low-level enemy I'm practicing against and having to go find another one.

I'm still not sure how to approach the acquisition of new spells though. Should it be learned from an older mage, or could it be accidently discovered in the wild? If the mage encounters a Fire Elemental, then they have access to a 'Fire' spell from then on after exposure to such a strong amount of this type of magic.

It's tough to give a good suggestion without a better idea of the game as a whole, target audience, etc

yeah, sorry, currently it's a single player live action RPG. Currently I'm thinking that every character would have the opportunity to learn magic (ie. there wouldn't be strict 'classes' as such), but it's there as a development path if the player chooses.

I'd like the game to have a lot of exploration, crafting and experimentation options within it - anything that is an interesting mechanic away from just killing things.

Having played Magicka, I'm worried about input mechanics for a spell-heavy action RPG. If you're making the casting as deep as this thread seems to indicate, then you might frustrate players when they are called upon to whip up an appropriate magical maneuver in the time they usually use to swing a sword. In Magicka, that usually leads to either long periods of kiting while deciding on a spell, or players just ignoring 90% of the possibilities and jamming out endless streams of identical spells, only changing their formula when they meet a hard counter for their primary weapon.

You didn't ask for input system advice, but I'm going to throw something out there: How about letting players pre-fabricate certain spells that they use frequently, and keep them on a "hot bar" or something, to be used like Duke Nukem uses different weapons? Instead of manually constructing and casting their spells, they could bottle them up and use them at will.

Going a little deeper down that rabbit hole, could you tie aptitude into that system as well? Make a distinction between "memorized" spells and "improvised" spells. In addition to being more convenient for the player to cast, a memorized spell might get a reduced cast time or mana cost, but the character's level puts a hard cap on the strength and complexity of spells that can be memorized. An improvised spell is clumsier to cast, takes longer, can be messed up by player error and costs the full amount, but it can be customized for the circumstances and you can make bigger, beefier spells this way than any spell you could have memorized.

So give them three or five or ten spell "slots" to store their usual go-to spells in, and then give them the tools to whip up something creative, at their peril.

Yo dawg, to put another rabbit hole in that rabbit hole, the memorization mechanic could be part of the spell system itself. That is, the ability to create a shorter "macro" for a longer spell is itself a spell.

Say you have four inputs (let's call them A,B,X,Y), every valid spell starts with A, and every pair {B,X,Y}x{B,X,Y} is a spell macro. (So memorized spells are quick to cast -- only two inputs -- but you only get nine of them.) Meanwhile, however, there's a spell schema A<spell><macro> that assigns <spell> to <macro>. (So if you wanted to assign the spell AXXBY to BX, you'd cast AAXXBYBX.) This spell type has the benefit of allowing you to change your macro strategy on the fly, but the downside is that it itself is a long spell with no immediate payoff.

Why not let the character learn new spells through killing the correct NPC, aka to learn a level 6 firespell he needs to kill a level 6 firedragon or something ?
(along with having the appropriate level i guess, then again, if you balance the strength of such NPCs well compared to what they can teach the character, i see no strong reason for level/XP requirements)