To get a good military quickly:
1) Embark with soldiers. These should be in proficient in a weapon skill, and have a defensive skill (shield user or dodger are solid choices). For reasons I don't fully understand, having high weapon skill dramatically speeds up training, also bear this in mind when recruiting immigrants - weapon skill is valuable so don't make them learn a new type of weapon.
2) Ensure all soldiers have a civilian skill at least novice, due to the bug where each month military dwarves without a civilian skill get an unhappy thought about being relieved from duty. Woodchopping is a good choice if there's nothing more productive to do, pump operating is another solid choice.
3) Create a uniform consisting of a weapon, helmet, cloak and shield at a bare minimum. Bring supplies on embark to produce these (may as well forge steel weapons and helmets from ore+fluxstone, it's a great investment), you might also want to bring bronze-making supplies for additional armor.
4) Produce waterskins or flasks to reduce drink-breaks.
5) Ensure each soldier has his or her own bed next to the barracks and give them a dedicated food stockpile in the barracks.
6) Put soldiers in squads of 2 or 3 and don't give them any time off. They need the training.
By eliminating all distractions from training you'll have legendary military dwarves within a year or two. Even doing everything right, the exact rate of training varies quite a bit, some dwarves seem just plain more enthusiastic than others.