The leveling system in Final Fantasy II is such that you tend to get better at things by doing them. Want to level up sword skill? Attack with a sword equipped. Want to get more mp? Spend a lot of mp. Some of the stats are less straightforward and one in particular is flat out weird. That stat is agility.
How do you get more agility? Win a fight with a high evade percentage. You don't need to be attacked. You don't need to have a long fight. You just need to end a fight (without a negative status condition). The higher your evade%, the better a chance you'll get an agility stat up.
How do you have a high evade%? Have a high agility...
Ok, that's not the only way. Like in the original Final Fantasy wearing armor decreases your evade%. The heavier the armor the more it reduces your evade%. So, one way to increase your odds of getting an agility up is to run around naked. None of my characters are currently wearing a helmet, body armor, or bracer.
Another way is to equip weapons and shields. It turns out almost every weapon in the game increases your evade%, and it does so in an awesome way. Almost all of them have a 1% evade stat but it turns out that stat actually gets multiplied by your skill level with them plus 1. So if I'm using a sword with 1 evade% and have 3 sword skill I actually get 4 evade% from it. (I imagine this is because you're parrying with the sword and the better you are with a sword the better you can parry with it.) Shields work the same way but have real evade% numbers. The starter shield has 4 evade% on it. Get a shield skill of 2 and that's an extra 12 evade% right there. Now, you have two hands in FFII and you can stick a shield in each hand so with 2 shield skill I'd actually get 24 evade%. And now if I attack I do no damage but get twice as much shield skill experience!
How do you get more agility? By running around the woods naked, holding 2 shields, and showing them to the imps until they run away. (Can you blame them?)