Getting STRONG fighters through promotion
Well, you already know that you need to reach LV10 to promote your fighters.  But there's more to a promotion than good looks...

First, promoting your character allows you to equip and use some more powerful weapons and items that could not be equipped while unpromoted.

Also, it allows your fighter to reach a Weapons Level 3.  Indeed, most of your fighters who join unpromoted are LV1 for one type of weapon, and LV0 for other types of equippable weapons.  While battling your way through the game, you will gain weapons levels.  While unpromoted, you can't reach more than LV2 for any type of weapon.  When you promote your character, he/she can reach LV3.  Increasing weapons levels adds to your attack power and gives you "special attacks" for that type of weapon.

Finally, when you promote your character, his/her status will increase more rapidly when he/she gains a level.
How do I use that to my advantage ?

Well, knowing the above facts, you can take advantage of that.  If time is not important to you, many things can be achieved:

Promote your characters at LV20

Maximum levels are LV20 unpromoted and LV99 promoted. Getting your characters to LV20 means they increase their status (MAX HP, MAX MP, ATT, DEF, etc.) every time they gain a level.  They also gain Weapons Levels. So they will be much stronger LV1 than if they had been promoted from LV10.

Equip many weapons

Most characters can be equipped with 3 or 4 different types of weapons. The idea is to equip a character with a weapon and use that weapon until it reaches LV2 (weapon level).  As soon as you reach LV2, switch to another type of weapon to gain experience with that type.  Since you can't reach LV3 while unpromoted, all experience gained at LV2 is useless, so use a LV2 weapon only when absolutely necessary.  I suggest you carry 2 types of weapons when possible, for short-range and long-range attacks (Sword/Knife, Lance/Spear, Axe/Hand Axe), so you're always ready.
Try to gain Weapon LV2 for every equippable weapon before promotion.  That way, when you promote, you only have to gain ONE weapon LV for each type.  And I gotta tell you, having Synbios LV3 on Knife + Sword + Blade + Rapier is a total rush !

So, when your character reaches LV2 of every possible weapon type AND LV20, promote him/her.  You'll appreciate it, this I guarantee...

Getting Weapons Levels

Well, this is still unclear, so here's my best guess.
When you're equipped with a weapon and you perform an action, you gain experience with that type of weapon.  It can be an attack, a counter-attack, a spell, an item used, and whatever action can be done either on friends (heal, antidote, increase status (attack/protect/resist), attack (while "possessed")) or on enemies (attack, counter-attack, decrease status (paralyze/sleep/illusion), magic item use ).

It is still unclear what is the precise determining factor in gaining weapons levels, since weapons experience is not shown
Fast promotion of magic users

Magic users such as Grace, Masqurin, Irene and Kahn, can increase their XP fast by casting spells.  A Heal spell gives 10+ XP to Grace, Irene and Kahn, but it has to be useful ( used on a character whose HP is full will give no XP, but if that character has just 1 HP missing, it's enough to get 10 XP).  Status spells (Support/Resist/Attack) can be used as often as desired, and the more characters touched by a single cast, the more XP each time.  Status spells are not cumulative, but the XP is... So if you're just building experience, use magic as much as you can. Until Masqurin learns the attack spell, give her the Ankh with Support magic.
These Boots are made for walking...

In Vagabond #1, you will find the Swift Boots behind Justin in the big tent.  Equipping the Boots raises AGL and DEF, but they can also be used to cast Support LV1 with no need of MP. 

Using the boots on a group of      will give the user
  5 characters                                7 XP
  4 characters                                6 XP
  3 characters                                5 XP
  2 characters                                4 XP
  1 character                                 3 XP
You can build XP with that, but remember to repair the boots as soon as they crack: you can't use them if they crack. You can also use the trick in the
Misc. Tips section to prevent the need of repairs.  Another pair will be available to buy in the DEALS from a supply shop later in the game.