Note: There may be more than one of each of the following materia. I am only giving you the first way.

AllElementalAdded EffectMP AbsorbHP AbsorbAdded CutMP TurboSteal as WellMagic CounterFinal AttackQuadra MagicSneak AttackCounter

All

In the Sector 7 Slums, visit the Weapon Shop. Go upstairs and into a room with a bunch of boxes in the corner. Just inside the doorway is a box containing your first All materia.

Elemental

In order to get this materia, you must tell Mayor Domino the password on your first raid to ShinRa HQ on the 62nd floor. Unfortunately, the password changes for every game, so I can't help you much more than that.

Added Effect

When you first visit Cosmo Canyon, you will go into the Gi Caves. When you reach the area with what looks like lava everywhere, take the first left. DO NOT RUN! Doing so will cause you to run into a wall of spikes causing nearly 500 points of damage to each teammate. Now, walk over the gold-colored liquid on the floor and go down. Continue until you reach a small balcony that you saw on the previous screen. On it will be the materia.

MP Absorb

Go to the item shop in Wutai after Yuffie and Godo argue. Inside is a treasure chest containing the materia. Unfortunately, Yuffie swoops down and steals it from you. No worries, however, because she'll give it back.

HP Absorb

When you enter Wutai, go straight north into a house full of cats. After you go through the Da-Chao ordeal with Corneo and Elena, go inside and climb up the stairs. In the attic you will find the HP Absorb materia.

Added Cut

I can't seem to find this one. If you know where it is, please contact me.

MP Turbo

After the fight with Jenova-DEATH on your first visit to the Crater, go into the next area. Jut about in the middle of your screen is a materia. Pick it up and you'll have the MP Turbo materia.

Steal As Well

On your raid on the Underwater Reactor, right before you board the submarine, there will be a box in the corner of the dock. Inside is the Leviathan Scales. Now, take them back to Wutai. Remember that cave on Da-Chao that had fire in it and you couldn't enter before? Use the Leviathan Scales on the flames and in the cave will be the materia.

Magic Counter

There is no definite way to get this. All I can say is you win it at the Chocobo Races.

Final Attack

This one is the same as Magic Counter.

Quadra Magic

REQUIRES A GREEN OR GOLD CHOCOBO. Go South-Southeast of Wutai, and you will find a peninsula nearly connecting Wutai Island to the Western Continent. There should be a greenish-blue colored cave on it. Inside is the Quadra Magic materia.

Sneak Attack

I can't seem to find this one. If you know where it is at, please contact me.

Counter

When you enter the Crater for the last time, continue through until the path splits. Take the left path. From here, the path will split again. Take the path in the upper-right part of your screen. Continue through until you come to an area with a bright shiny hole (actually a fountain from which materia is formed) in the center. In the middle of it is the Counter materia.