What exactly do MP3 repairing programs do?

Multimedia file have usually a complex structure which includes headers, which are basically sequences of bytes whose length is specified in the MP3 file. Some segments of the file contain pointers to other segments, or their own length.

Sometimes a byte is damaged or the end of the file is missing, making the file impossible to use by a player.

In this case, the repair program will try to heuristically identify the sound sequences in the file from their contents, rather than by pointers, and will reconstruct around them the required headers for this to become again a legal MP3 file. You are of course not guaranteed afterward to have all the sound back or all the information required to play it correctly. This is more a salvage operation than repair.

They fix or remove bad tagging data. Some players choke on it. If it can play in VLC, it's close to okay, but has something in it that Media Center or iTunes (for example) cannot handle. They cannot fill in damaged music data.