The Materia that you pick up and equip throughout the game can grow and level up just like your characters. Its growth and ability to level up is dependent on how much AP you earn after each battle (which is listed as one of the line items on the conclusion screen). AP stands for Ability Points and certain weapons will allow your Materia to grow slower, faster or not at all.
You can see how much AP you have earned on each Materia as well as how much AP is needed to reach the next level by selecting the “Materia” option in the menu screen. As you level up your Materia you can gain access to new, higher-level abilities and spells. For example, leveling up a Restore Materia will gain you access to the new spells listed under the “Ability list” section in the example screen below:
Some Materia, such as Ultima Materia and Shield Materia, need to be leveled up to at least Level 2 before you gain access to any abilities at all (which, in the cases of Ultima and Shield Materia, are definitely worth investing the time to grow as the spells you receive once they level up are very powerful and very helpful).
The amount of AP your Materia receives after a battle is dependent on the “Growth” stat of either the Weapon or the Armor that you attach your Materia to. For example, Cloud’s initial weapon, the Buster Sword, offers “Normal Growth”. This means that if you earn 20 AP at the end of the battle each Materia equipped to the Buster Sword will receive 20 AP. There are other weapons that offer higher and lower growth - for example, Cloud’s Apocalypse Sword offers Triple Materia Growth, while Cloud’s Ultima Weapon (and all Ultimate Weapons in the game for that matter) offer no Materia Growth. This means that your Materia will not level up when you attach Materia to Cloud’s Ultima Weapon (but could still level up if you attach it to his armor).
You should make every attempt to use weapons that offer Double or Triple Materia Growth when you find them as long as they do not impact your character’s overall Attack Power too heavily. This includes:
W Machine Gun
Only Cloud and Cid have weapons that offer Triple Materia growth. This makes them best suited for leveling up your Materia as quickly as possible. For more information on how to level up your Materia by the most efficient means possible check out the Leveling Your Materia section in the Tips and Tricks Area.