It's not random at all. The way stats work in FF2 is that they each have their own level. Using that stat causes it to gain "experience". Getting hit raises your HP as well as your endurance. Casting black magic causes your MP and intelligence to rise. Casting white magic also raises MP, but it raises spirit instead of intelligence. Attacking an opponent raises strength. Targetting an opponent for attack raises accuracy. Having a spell cast on a character will raise his or her magic defense. But agility? Just get targetted by an attack. So a character attacking him/herself would be raising his/her strength, accuracy, endurance, HP and agility, as well as getting more proficiency in whichever weapon they are using.

As for WHEN you get these level ups, it's like I said about "experience". Let's say you need to lose 100 HP to increase your HP. You get into a battle and lose 20 HP. This means you need to lose 80 more. Even if you restore that character's HP, you will still only need to lose 80 more. Let's say the next battle you lose 78 HP and almost die. You restore HP, but still only need to lose 2 more HP. Let's say your next battle is with a Hornet and you lose 3 HP. Your HP will then rise at the end of battle. I don't know how getting KO'd factors in, if it factors in at all, but I think it's possible that being KO'd in battle undoes any damage you've taken.