Enemy Skill materia can be found in the Shinra Building, Junon Beginner's Hall, Forgotten Capital, and in the Chocobo Sage's house (talk to the green chocobo).
To learn an Enemy Skill, equip an Enemy Skill materia to one of your party members. In battle, an enemy must use the skill on your party member in order for the materia to learn it. Then any party member equipped with that particular materia, can use that Enemy Skill.
N.B. Some Enemy Skills, particularly defensive ones like Big Guard, require manipulating the enemy in order to have them use the skill on your party member(s). Use the "Manipulate" command; the "Hypnocrown" accessory can also be useful. It should also be noted that you can't use an Enemy Skill on an ally in order to have them learn it.
N.B. Be careful with Trine, as this is the one Enemy Skill that is missable. You may want to save the Pagoda battle against Godo in Wutai until you are fully prepared, i.e. until you have all 4 Enemy Skill materia including the one from the Chocobo Sage's green chocobo. Be aware that you cannot learn Trine in the Gold Saucer Battle Arena, even though you can encounter a Stilva there.
Enemy Skill List
Non-elemental damage to all opponents
Learn from: Custom Sweeper (Midgar Area, World Map), Death Machine (Junon), Bullmotor (Corel Prison)
Causes [Critical/Small] with levels in multiples of 4
Learn from: Mu (Chocobo Farm Area, World Map), Trickplay (Bone Village Area, World Map)
Non-elemental damage on any one opponent, the HP damage inflicted is equivalent to the number of times party has escaped from battle.
Learn from: Chocobo (Find a chocobo with a level which is a multiple of 4, such as a Level 16 chocobo near the Chocobo Farm Area - these will always appear alongside 2 Levrikons. Feed it some Mimett or Sylkis Greens, then use L4 Suicide)
Quite powerful Fire damage on all opponents
Learn from: Midgar Zolom (swamp near Chocobo Farm, World Map)
Learn from: Zemzelett (Junon Area, World Map - note that you can't actually learn this until you get Cait Sith in your party and the Manipulate materia), Wind Wing (Whirlwind Maze)
Adds [Barrier/MBarrier/Haste] to every ally
Learn from: Beachplug (Costa Del Sol Area, World Map; Gold Saucer Area, World Map - again, note that you can't get this from a Beachplug enemy without first having the Manipulate materia), Wolfmeister (North Corel train during Huge Materia sequence)
Quite powerful Water damage on all opponents
Learn from: Harpy (Gold Saucer Area, World Map), Jenova LIFE (Forgotten City), Serpent (Sunken Gelnika)
Lessens one opponent's HP by 1/2, doesn't tend to work on stronger enemies
Learn from: Death Claw (Corel Prison), Dark Dragon (N. Cave)
Causes [Sleepel/Frog] on one opponent, doesn't tend to work on stronger opponents
Learn from: Touch Me (Gongaga Area, World Map), Toxic Frog (Temple of the Ancients), Christopher (N. Cave)
Pronounces death sentence on any one opponent - stronger enemies are usually immune to this
Learn from: Gi Spector (Cave of the Gi), Sneaky Step (Cave of the Gi), Boundfat (Corral Valley)
Does damage equal to user's maximum HP minus current HP
Makes any one ally immune to death (i.e. the Sudden Death status attack, it doesn't mean the party member in question is immune to KO. To become immune to KO, equip either a Phoenix-Final Attack or Revive-Final Attack materia combination...
Learn from: Adamantaimai (Wutai Area, World Map)
[Poison/Confu/Sleepel/Silence/Small/Frog] on all opponents, very strong enemies will be immune...
Learn from: Malboro (Gaea's Cliff, N. Cave)
Powerful [Fire/Ice/Lightning] damage on all opponents
Learn from: Stilva (Gaea's Cliff), Parasite (N. Cave)
Somewhat powerful non-elemental damage on any one opponent
Learn from: Goblin (Goblin Island, World Map)
Big non-elemental damage on any one opponent
Learn from: Ultimate Weapon (Cosmo Area, World Map), Ruby Weapon (Gold Saucer Area, World Map), Dragon Zombie (N. Cave), Safer-Sephiroth (N. Cave)
Raises the Defense and Magic Defense of one ally
Learn from: Dark Dragon (N. Cave)
Revives, fully restores HP to, and removes abnormal status from, any one ally
Learn from: Pollensalta (N. Cave)
Causes [Death] on enemies with levels in multiples of 5
Learn from: Parasite (N. Cave)
Randomly pronounces death on any one opponent or ally
Learn from: Death Dealer (N. Cave)
Big non-elemental damage on all opponents, ignores defense.
Learn from: Dragon Zombie (N. Cave)
Most Useful Enemy Skills
Matra Magic - You can learn this right after leaving Midgar, it costs little MP for its high potency, and also it's non-elemental - super.
Beta - This is extremely powerful considering how early you can learn it. Equip an Enemy Skill materia and fight the Midgar Zolom - the Zolom will tend to fling one of your party members out of the battle, allowing that party member to survive, and then use Beta. This allows you to learn Beta without having to actually defeat the Zolom, but it isn't guaranteed to happen every time you face the Zolom...
Big Guard - Again, you can learn this in Disc 1, as soon as Cait Sith joins your party with the Manipulate materia; it casts Barrier, MBarrier and Haste on all party members for just 56 MP. This is better than the spell "Wall", which you can learn from the Barrier materia - Wall doesn't include Haste and costs 58 MP.
Aqualung - This is also very powerful considering how early you can learn it.
White Wind - This can also be learnt on Disc 1 - again, after you pick up Cait Sith and the Manipulate materia, you can take the boat back to Junon and encounter the Zemzelett in the Junon Area. White Wind can be hugely useful for healing your party members for low MP cost.
Shadow Flare - This is one of the most powerful spells in the game.
Angel Whisper - This works the same as either Life 2 or Full Cure, but for half the MP. It will also fix any status ailments - icing on the cake.
Pandora's Box - Similar to the spell Ultima, but costs far less MP.
As you can maybe see from above, there is a strong tendency for Enemy Skills to be overpowered when compared to "standard" magic spells from (green) Magic materia.