Soldiers are stupid.

Hopefully you haven't given up hope on this thread in the past week. Soldiers evolve based on a unit leader and his/her accumulation of soldier points. Soldier points are based on how many soldiers are in the unit. If I have a unit with a fighter, 3 sets of soldiers (so 9 little guys) and a Sorceress unit leader, every time that unit wins a battle (you have to win battles to accumulate soldier points) that unit leader will get 9 (3 sets of soldiers multiplied by 3 soldiers per set) soldier points at the end of the battle. Once the unit leader has gained 100 soldier points, one of the sets of soldiers is promoted to a fighter/amazon based on the gender of the unit leader and whether or not the unit is carrying an Ansate Cross (which of course, would reverse the gender). Be warned however, that if one of your soldiers dies (for instance, a soldier set loses 1/3 its hp and only 2 individual soldiers are left) then you only get credit for the 2 soldiers who are alive. Thus, if you "count heads" at the end of a victorious battle, add up all the little guys you have in your unit and that will be the amount of soldier points you accumulate for that battle.

Additional note: for a unit leader to become eligible for promotion to Centurion, (s)he must have promoted 7 soldiers into fighters/amazons (note however that centurions and legions are rather useless so this is not recommended).