what i did was this:

Cloud: Ultima (as soon as I got it), 3 Elementals (early-mid game), E.Skill (always), strongest summons I had, 2xCut, other stuff.

Aeris (before dying): Cure (duh), FullCure (maybe), Esuna (or whatever materia had Esuna), mostly non-offensive magic.

Vincent: Comet, Poison, other less important offensive magic, support stuff.

Yuffie (after Aeris dies): Cure, Esuna, around the same as Aeris.

Of course, all should have summons, commands, and whatnot.