There are three things to level up in this game. The first is your experience level, which will raise your stats when it goes up. Harder enemies give more experience, generally, so you'll be gaining levels at a steady rate throughout the game. All three characters get the same amount of experience for a slain monster, regardless of who struck the final blow.
The second thing you might want to raise are your weapon levels. Each character has individual levels for each of the eight weapons you come across. A weapon can only be raised as high as as many orbs it has been forged with plus one. Increasing a character's weapon level will allow him or her to charge up an attack to a high level. Experience is divided up for weapons a little differently than the experience for raising regular levels. First off, it is easier to raise lower weapon levels than it is to raise higher ones. For example, killing a rabite with your sword at level 0 might get you 8 points toward the weapon's next level, but killing a rabit with your sword skill at level 7 will likely only get you a single point towards the next level. This offsets the fact that you need 100 points between each skill level, making it take progressively longer to reach each successive level. Also unlike regular experience, killing an enemy will not net each charact an equal number of points to each character. The character who strikes the finishing blow will receive the full amount of points toward his weapon's level, and the two other characters will receive about half of what they would have received if they had killed the enemy themselves. Finally, though this should be self-evident, only the weapon that is actively equipped on each character will receive any experience.
Magic experience works similarly to weapon experience in the rate of progression. Each casting of a spell nets experience, and there is no difference whether an enemy dies from it or not. Only the girl and the sprite have magic, and each have seven elementals each with their own levels to raise. Casting any of the elemental's spells nets that elemental the same amount of experience, regardless of the MP used to cast it. Raising an elemental's level will increase the efficacy of all the spells that elemental commands, with effects including increased damage caused, longer durations of status effects, and so on. An elemental's level is limited by the number of Mana Seeds your party has sealed, so by the end of the game the maximum level of each spell is 8:99. Once an elemental reaches level 8, its normal animation will sometimes be replaced by a different, longer one, and the spell will be even more effective than normal. If the elemental is at 8:99, this special form of the spell will happen almost every time it is cast.
So the benefits of raising your levels of all sorts should be obvious. For the most part you don't need to stop to specifically level up to advance in the game. If you do want to, however, here are some spots I recommend:
Upperland Forest - This is the first and most economic area for you to raise weapon and magic levels. Just run around the different-seasoned woods killing things, and when you run out of MP or need your health restored, stop by the Wind Palace and talk to the sprite's grandfather to have all your hp and mp restored for free. The only disadvantage is that the level experience the enemies give won't be worth much later in the game.
Lofty Mountains - Not a bad place to level at when you first arrive. You can run around killing things and stop off in Mandala to rest at the inn when you need to be healed. You get more regular experience than in the Upperland Forest, though overall it is a slower process.
Mana Fortress - In my opinion, the best place to level up your normal levels and the Sprite's magic. The enemies give great level experience, and the sprite can use its MP Absorb spell to constantly replenish its magic resources. Level the girl's magic back in the Upperland Forest, though.