Military training in the Hijaz during early Islamic era

"The Muslims at the period were also very experienced in warfare" said Muz, and I think that is the key, even on day one of the period. If you can lead a caravan of spice across the desert, defending it from other tribes, you already have all the cavalry skills you need. In exactly the same way, the Sioux in their day were called the world's finest light horse, and they learned from hunting buffalo and raiding other tribes. Don't underestimate the training value of fighting amongst brothers.

A good point of departure is the wiki page on the Rashidun Army, which gives an overview of early Islamic infantry and cavalry. Also, the Military Legacy section of the Khalid ibn al-Walid wiki entry has some great info on the organization and makeup of his armies.

The "Mobile Guard" is especially famous - the exceptionally quick Islamic light cavalry.

I'd put it down to zeal - the Rashidun Muslim armies were literally fearless and welcomed death. Any reference to Muslim armies of the period by Rome/Persia noted their fearlessness. There was a strong sense of camaraderie down command chain, in that the lower ranks of soldiers knew what they were fighting for. Compare this to the Persian system which utilized a lot of slaves.

Khalid al-Walid is one of the most brilliant generals throughout history, and his strategies pivotal to the early grand victories against the Byzantines/Persians. Khalid was undefeated, even when fighting against the Muslims earlier on. One such notable battle was the Battle of Mut'ah, where Khalid took leadership later, when Arab army of 3,000 soldiers was defeated by well over 10,000 Roman soldiers. This is where he earned his title of Sword of God. Or the Battle of Yarmouk, where Khalid defeated about a hundred thousand Byzantines with around twenty thousand soldiers.

While Khalid was later sacked, his victories had already crippled the military engines and morale of Byzantine/Persia.

The Muslims at the period were also very experienced in warfare. They started with a single city-state (Medina), and through wars and diplomacy conquered the Arabian peninsula. After Muhammad's death, the Arabians under Caliph Abu Bakr had to take back the region from rebels and 'false prophets'. The Ridda Wars involved over a dozen battles within a year, spread throughout the Arabian peninsula.

I could find little note of military during the early Islamic era, but with the very tight timeline between Muhammad's migration to Medina, their conquest of the Arabian Peninsula, and the wars during the Rashidun Caliphate, it would be fair to assume that the Muslim armies had on the job training!

Hijaz

Hijaz only a small part of Arabian Peninsula situated on Eastern bank of the Red sea. Arab groups understandably varied in their laws and customs throughout the region.

Who was the Power in Hijaz

In Hijaz, main power was the City state of Mecca. In fact, Meccans were the most prominent people among the Arabs due to being custodians of Kaaba. Meccan natives belonged to tribe of Quresh even though there was a regular presence and settlements of foreign elements in form of traders, pilgrims & slaves. It might be of interest to you that Muhammad belonged to tribe of Quresh and city of Mecca.

Division of state affairs in Mecca

Quresh had systematically divided the different affairs of the state among different branches of tribe. All these clans trained their youth in the affairs they were charged with.

Since we are discussing military only so we will focus only on branches which had military responsibilities.

1. Banu Abd ad-dar: They were responsible for carrying and guarding the Meccan flag in battle.
2. Banu Umayyad: They were charged with political command of the city even though they vied with their cousins the Hashemite for that.
3. Banu Makhzum: This was the power-house of Mecca. This house was charged with defense of Mecca and leading her Armies. Many of the greatest generals of subsequent Islamic Caliphate belonged to this house e.g. Khalid Bin Walid, Akrimah bin Abi jahal etc.

Custom of sending kids away to foster with bedouins

There was a custom among the city nobles to send their children to live with bedouins in desert for some time in order to learn survival skill, improving their physical state and hardening them up. Muhammad himself lived for a time with a bedouin family.

Training at Arms

Training that Khalid bin Walid recieved as a child should give you an idea. From wikipedia:

As a member of the Makhzum clan, who were amongst the best hors*m*n in Arabia, Khalid learned to ride and use such weapons as the spear, the lance, the bow and the sword. The lance was said to be his favorite among the weapons. In youth he was admired as a renowned warrior and wrestler among the Quraysh.

Now Khalid was son of a notable noble so of course not every boy was going to be as fortunate as him when it came to training. But it shows you that his training seems to be by no means inferior to that received by a Greek noble in Constantinople or a Persian noble in Persepolis.

Unlike rich Khalid, his Cousin Umar who eventually became second Caliph of Islam belonged to middle class. For his training wikipedia says:

According to the tradition of Quraish, while still in his teenage years, Umar learned martial arts, horse riding and wrestling. He was tall, physically powerful and a renowned wrestler.

Now we have established that at least people from upper and middle classes received martial training.

Arabian background

The Arabs before being united by Islam were in continuous warfare against each other. Feuds over water-rights and minor insults lasted for centuries. Even when threatened by a bigger and organized power such as Kingdom of Aksum, Arab tribes destroyed the invaders. (Yes Islamic traditions say that it was God who destroyed them but we are not here to discuss that. Since we know an invasion did happen and it was successfully repulsed, we can only assume it was the Arabs who did that).

What Arabs lacked was a unity and system. Otherwise they had fought countless wars with weapons comparable (At least to most extent) to their more developed neighbors. Arabs knew how to successfully exploit terrain (As Medinians did in Battle of Badr), how to successfully use cavalry to force a general rout (As Khalid bin Waleed did against Muslims at battle of Uhud), how to create fortified obstacles in path of an enemy (As Muslims showed in Battle of trench), how to carry out a siege (As Muslims showed against Medinian Jews) and there was no one in world who could teach the Arabs how to ride and how to raid. They used swords, Javelins, spears, scimitars, helmets, shields, daggers, siege equipment etc. just like their neighbors did.

Islam provided them with a system and union and thus they spilled out of their peninsula and ran over the ancient Persian and Eastern Roman Empires.

Wars with Neighboring Empires

Eastern Roman Empire and Persia surely had bigger and more established forces but they had been weakened by warring against each other and also due to incapacity on top of the leadership. Thus they were unfit to defeat the hardened hors*m*n pouring out of Arabia. Same thing happened with Arabs themselves when Mongols descended from the Steppes.

Between the two Empires, Persia was most vulnerable. They were plagued with corruption and weakened by court intrigues and fighting among royal dynasty. Which is why unlike Eastern Romans, Persians were completely conquered.

Superior tactics and Generalship

First Muslim commander on Eastern front decisively used his mobility to collect intel for a major invasion. Persians failed to issue an appropriate response.

Later when general invasion occurred, Persians were completely outmaneuvered by superior tactics of Khalid bin Walid which were state of the art. Khalid is not listed among best generals ever for nothing. For example in Battle of Chains, Khalid showed us the power of mobility over equipment. Persians were heavily armed and armored which hampered their speed. Khalid focused on their disadvantage and gave the Persians a merry chase until they were tired to bones. Then Khalid made short work of them. Khalid also knew exact movements of Persians while he successfully deceived the Persians in locating himself. So he employed intelligence and spy operations as well. Pictured below, Graphical representations of the Maneuvers employed By Rashidun (Red) and Sassanids (Blue) in Battle of the Chains:

Later in Battle of River, Khalid again exploited his mobility and attacked the Persians before they could assemble. Persians again showed absolute lack of strategy and military sense.

In Battle of Wallaja, Khalid executed a master piece of Double envelopment or Pincer movement and defeated numerically superior adversary, showing generalship comparable to Hannibal's in Battle of Cannae. Graphical representation of the battle and troops movements below (Red Rashidun and Blue Sassanids):

One of my personal favorites of Khalid's strategies is the one he deployed in Battle of Maraj-Al-Debaj. He defeated a Byzantine force which was twice the size of his own force with mobility and surprise. He divided his meagre 4,000 mounted lancers into four units of 1,000 men each and launched consecutive attacks from all sides to surprise and encircle the 10,000+ Byzantine Soldiers, commanded by Emperor's son-in-law himself. He won another crushing victory. Following gif will show you the battle:

Khalid fought more than a 100 battles and never lost a single one. How many generals can boast of that and what does that tell one about training and aptitude of such a commander?

It must be noted however Muslims were lightly armored unlike Persians but they made it play to their advantage.

As already pointed out by SwampYankee, you should visit the page on Rashidun Army, you would see they had the same technology as their adversary and even better organization and strategy.

So to conclude things:

1. Muslims had better generalship than their adversaries.
2. Muslims were trained in contemporary martial skills and veterans of many a civil wars.
3. Muslims were united under the first Caliphs.
4. Muslims deftly used all the weapons their foes used and at strategy they beat them.
5. The great Empires however enjoyed advantage in terms of resources and numbers. They had also equipped their soldiers in a better way. But they were used to set-piece battles from their experience of fighting each other and they were not ready to face the medieval Blitzkrieg that the Arabs brought with them. Same thing happened with Arabs when they focused too much on static doctrine and got conquered by mobility focused Mongols. The defeats did not stop until Mamluk Turkics of Egypt defeated the Mongol Turkics in Battle of Ain-Jalut to halt their advance further Westwards towards North Africa (It was the first time a Mongol Advance had been halted).