Leveling up characters can be done in the same manner as leveling up your Materia with AP. Check out the Materia Leveling section of the tips and tricks area for more information and head to the Northern Cave to level both at the same time.
An alternative strategy is to fight monsters and enemies in the Sunken Gelnika. Check out the Sunken Gelnika section for more information about where to find it.
You can also find a small area just south of Cosmo Canyon called “Cactus Island” which can be used to level earlier on in the game.