Levelling up characters can be done in the same manner as levelling up your Materia with AP. Check out the levelling Materia section of the tips and tricks area for more information and head to the Northern Crater 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.