The most efficient way to level up your Materia is found within the Northern Cave. The area that you are looking for is the upper-left pathway. If you have been following this guide all the way through, it is the area that you send Tifa to alone. It can also be seen in the screenshot below:

You can travel back down to this area and still climb back out of the Northern Cave so don’t worry about getting stuck part way down.

The enemies that provide the most AP are Magic Pots and an enemy called a Mover (which looks like a small orange ball). Both creatures are pictured in the screenshots below:

Note that in order to kill a Magic Pot you will first need to feed it an Elixir. As a result, you will have to stock up on Elixirs. The best method to do this is to utilize the W-Item Materia item duplication trick. Check out the Cheats section for more information.

The Magic Pot battles offer you the perfect opportunity to do this as they will not attack you in battle and will just shout “Gimme Elixir!”.

Each Magic Pot you kill will net you 1,000 AP and each Mover is worth 600 AP. Movers only come in groups of three which means you will receive 2,400 AP each time you encounter them.

Don’t forget to equip your Triple Growth weapons such as Cloud’s Apocalypse and Cid’s Scimitar to speed up the leveling process.