There have been quite a few other threads in the past month or so on this, you could probably find a few good ideas in those others. Like others have said, it's important to specify WHY magic is rare. Anyway, ones I liked:
1> Require a Feat to enter each spellcaster class. (I've actually used this one, BTW). That is, make a feat called something like "Arcane Talent" that lets the person know three cantrips and cast 2/day. Anyone who wants to be a Wizard, Bard, or Sorcerer needs to have taken that Feat. There's a separate one for the Divine classes (Cleric/Paladin), one for the Nature classes (Druid/Ranger), and one for the Psionic types. So, first off it keeps people from taking spellcasting classes at level 1, since you can't pick Feats until AFTER you've picked classes. Also, it's a Feat, so you're spreading them a bit thinner.
If you want to make it even tougher, break magic into 5 "power ranges": 0, 1-3, 4-6, 7-9, 10+. Then, make it a Feat to enter EACH range. So, Basic Arcane Talent would give you the cantrips and unlock 1-3, Intermediate Arcane Talent unlocks 4-6, Advanced Arcane Talent unlocks 7-9, and Epic Arcane Talent unlocks 10+.
This one makes high-level mages far less common, but the magic itself is still just as potent.
2> Add a lot of material components, especially expensive/rare ones. If a Fireball needs a little bat guano it's no biggie, but if it needs enchanted Red Dragon guano things get a bit more complex. Suddenly, it's not a given that every level 10 Wizard has Fireball available. The spell's still just as potent, it's just not going to be as common.
You also need to do this for the divine versions of spells. Just because the caster is a priest doesn't mean he doesn't need a Red Dragon tooth to cast Flamestrike.
Adding foci helps too. Sure, the caster will go buy/make/find whatever foci he needs, but that takes time and he's not going to haul tons of trinkets along... or will he? Suddenly all those shamen with necklaces of teeth and feathers make more sense.
3> A level X spell always does X damage to its caster (or maybe 2*X with a Will save for half), which triggers an immediate Concentration check. So, first it means he'll probably fizzle some spells. Second, he can't just cast continuously without wasting healing spells on himself, which means it'd be nice to have some weapon skills. Third, you'll want high HP to soak up the spell damage, which means multiclassing with a fighter class... see the effect?