If you pair it with a materia that has an elemental property, it will have an effect on your weapon/armor. If you pair it with Fire on your armor as ProjectD said, you will either lessen the blow of a fire based attack or absorb it depending on how much leveled up the Elemental materia is. If you it with Ice on a weapon, it will make your attack stronger against enemies weak against Ice. You can use this materia with many of the magic materias: fire, ice, lightning, earth, gravity, poison. I'm not sure what might happen if you pair Elemental with a Master Magic materia. I'm not sure if they level of the magic materia has anything to do with how the Elemental materia will work or not. You can also pair Elemental with most of the summon materias, as many have elemental properties to them. If you are low on Ice materia and want to give someone defense against Ice, you can pair Elemental with Shiva on an armor and it will have the same effect. You can pair Elemental with Leviathan, one of the only ways to attack with/defend against Water attacks. The same with Alexander and Holy attacks.

Just to note, I think that poison is both an element and a status in this game. I don't really know what the difference is between pairing Poison with Elemental or Added Effect.