From Bulbapedia, the community-driven Pokémon encyclopedia.
A move relearner (Japanese: わざおしえマニア Move-Teaching Maniac) (not to be confused with a Move Tutor) is a character who allows Pokémon to relearn any move that they were able to learn from a previous level-up (usually in exchange for a Heart Scale). Reasons for this include none of that species being able to be obtained at an early enough level to actually learn the move in a particular generation (e.g. Zapdos and AncientPower in Generation IV), or the species starting with more than four moves (e.g. Kecleon).
One limitation is the move relearner is restricted to the particular moveset associated with the Pokémon's species (i.e. current evolutionary form). Many Pokémon, especially those that evolve by way of evolutionary stone, have access to moves that their evolutions do not, such as with Eevee, who can learn Take Down by level though none of its evolutions can.
Conversely, certain Pokémon evolutions have access to moves that they (and their pre-evolutions) could not actually learn at the particular level, like a Charizard learning Heat Wave at level 1 despite that it does not attain this form until level 36; a move relearner is the only way to teach the move.
The move relearner cannot overwrite HM moves.
Generation II has no formal move relearner. However, as a reward for beating the Elite Four and Champion at the Gym Leader Castle on Pokémon Stadium 2, the player was given the opportunity to make one of the Pokémon involved in the battles remember a move.
Generation III introduced a man in Fallarbor Town, who allows a Pokémon to relearn a move. The service is not free, however. He will only perform the service in exchange for a Heart Scale. Some of these may be obtained in the course of the game; the rest must be obtained from wild Luvdisc.
A man on Two Island also allows the player to have a Pokémon relearn a move. The price is different from Ruby, Sapphire and Emerald, however. Instead of a Heart Scale, either two TinyMushrooms or one Big Mushroom must be given. This is likely due to Luvdisc not being native to the Kanto and Sevii Islands regions, while Paras and Parasect are.
A man inside the Mt. Battle lobby serves as Orre's move relearner. He will teach a Pokémon a move it could have previously learned for 1,000 Poké Coupons.
Much like the man in Fallarbor Town, a man in a house northeast of the Poké Mart in Pastoria City will teach a Pokémon a move it could have previously learned but has not, in exchange for a Heart Scale. A large quantity of these may be obtained underground. It is still possible to collect them from wild Luvdisc, but only after the National Pokédex is acquired. In Pokémon Platinum they can also be obtained daily in Solaceon Town by helping with the Pokémon News Press.
In a house in Blackthorn City, there is a man who will exchange Heart Scales for the use of his move relearning services. He is conveniently located in the same house as Johto's Move Deleter and a Move Tutor. Heart Scales can be obtained from destroying rocks with Rock Smash, and through using a Pokéwalker. They can also be obtained as a Pokéathlon prize for 1000 points on Wednesdays and Sundays or from a Pokémon that has Pickup and is at level 51 or higher.
In a house near the Pokémon Center in Mistralton City, a girl known as the reminder girl will give the player the possibility of relearning a move a Pokémon could have learned before, in exchange for a Heart Scale. Next to her is the Move Deleter. In these games, Heart Scales can be rewarded in Driftveil City daily*, exchanged for 10 Sweet Hearts in Mistralton City, held by wild Luvdisc, and in the Sparkling Sea. In addition, Pokémon with Pickup at level 51 or higher may occasionally hold Heart Scales.
Both move relearner and move deleter were relocated to Pokémon World Tournament.