What level do my characters need to be at, to get promoted?
Characters need to be at least level 20 in order to be promoted. Since experience points are carried over from level to level (eg, you have 80 exp, gain 40 exp and go up a level... you're then 1 level higher and have 20 exp - in Shining Force 1, the experience was reset to 0 when you gained a level), you should find levelling-up to be easier than in the original Shining Force.
Characters can go up to a maximum of level 40 before promotion, and up to 99 afterwards. Many people question why you'd want to level up to 40 before promotion. Well, here's why:
Because you've had 20 extra level-ups, you have 20 extra stat increases.
Think of it this way, if you promote at 20, and then get a character up to level 99 after promotion, that's 119 levels. If you got 2 HP per level-up, that's 238HP for that character.
If you promote at 40, and level up to 99, that's 139 level-ups. If you got 2 HP per level-up, that's 278HP for that character. That's an extra 40HP that you wouldn't have if you hadn't promoted later.
The same goes for the other stats of course. The more levels you gain, the higher your stats. The higher your stats, the stronger your characters. So, the more levels you gain, the stronger your characters.
Of course, it's easy enough to complete the game without levelling up, but it can add extra life to the game if you play through it again, trying to max-out all your characters' stats!