What if you mentioned something about it in the training room above the weapon shop upstairs in Sector 7?
Infodumps don't really help people all that much. For things like this, a more practical or direct example would be better. As far as I'm aware there are two Elemental materia in Midgar, one in the Mayor's office, another somewhere I forget. If my awareness is right, this scenario could work.
A side boss can be added at a point like Jenova's escape, have a Shinra soldier comment about how they threw literally everything they had at it and it's only harmed by Holy. Because their weapons can't link materia and they only had one holy elemental item, the party will have to do it. Then have him fork over an Elemental (and a Restore if you don't have it for some reason), explain how it works and how to tell what materia has what element.
If my awareness is wrong, this boss could be placed elsewhere and the second Elemental moved appropriately.
This gives the player an explanation followed by a practical example that is needed to proceed. It also reinforces the idea that elemental affinities are king.
Alternatively, have a random NPC say he had the idea to link Restore to Elemental on his weapon so he could heal his allies with physical attacks (a concept which is already established with Aerith), but it backfired and he has no friends anymore, but he has an easier time fending off ghosts from the train graveyard at least.
First is more direct, second needs interpretation and experimentation. Downside to the first is that people
who don't freaking read will think "This boss is bugged nothing hurts it". Downside to the second is that people will come to the conclusion of "Restore = Element only hurts undead".
