When Islam first came around it spread amazingly quickly, at least in the sense that a lot of territory came under caliphate control very quickly. Was this purely through military might or was it not uncommon to see people newly brought under the caliphates convert without a fight?
You're absolutely right that the expansion of territory under the control of Muslims happened very quickly and through military conquest! However, scholars differentiate between Arabization and Islamicization (or Islamization) of conquered territories. It generally happens that conquest preceded the gradual acculturation of Arab culture which preceded the bulk of local conversions to Islam.
Here are three earlier answers of mine that address the complexity of Arabization, Islamicization, the status of "peoples of the Book", and the possibilities of forced conversion:
Hopefully this will get you started!
(1/2) Great question! The expansion of Islam came in several different stages, so I'm going to address those each in turn. The short answer is that when Islam came to newly conquered lands, they often left the population to their original beliefs, not requiring conversion (notably for the People of the Book - Christians, Jews, at times Zoroastrians, etc). However, the population normally found it within their interests to convert on their own, leading to a gradual "Islamization" of the Middle East.
From Revelation to Medina
The phrasing of your question implies that you're asking about the spread of Islam out of the Arabian Peninsula, but we may as well start at the beginning to gain a comprehensive picture.
In 610AD, when Muhammad was 40, the Revelation of the Qurʾan began. This revelation would continue until his death in 632 with two distinct phases: the Meccan Phase and the Medinan. The Meccan verses were revealed between 610 and 622, when Muhammad was just beginning to preach in his home city of Mecca. At this time, Muhammad was in a socially weak position. Despite belonging to the Quraysh, the ruling tribe of the city, Muhammad’s ideals threatened the livelihood of the city. Mecca, and the Kaʿba in particular, was a pilgrimage hotspot for the Arabian polytheists, yielding quite substantial tribute as well as making Mecca a trading-hub in Arabia. At this time, Muhammad was largely protected by his Uncle, Abu Taleb, and first wife, a rich merchant named Khadija.
Conversion to Islam at this point in time was entirely voluntary. This is reflected in the parts of the Qurʾan revealed when Muhammad was in Mecca, which emphasize the Will of God, moral values, and takes a generally non-combative tone. The surahs are typically shorter, then to not contain rules or calls to struggle (jihad), and are rather overarching calls to faith.
Muhammad was increasingly persecuted by the inhabitants of Mecca and began to look outward for another city in which to live and preach. In 622 AD, after several failed attempts (such as being laughed out of the oasis town of Taʾif) and having to flee an assassination attempt at his home in Mecca, Muhammad was invited to settle in a town called Yathrib, which would later be known as Medina.
The inhabitants of Medina at this time were a mix of polytheists, Jews, and some Muslims (during the annual pilgrimage to Mecca, Muhammad converted a group from the Banu Khazraj in Yathrib, and they continued to spread Islam within their own town). It was a group of these Muslims who invited Muhammad to their town to act as a judge and arbitrator between the tribes. The tribes of Yathrib had been warring on an off for over a century, with a large battle having taken place just 2 years before in 620 AD.
Shortly after arriving in Medina, Muhammad drafted what is known as the Constitution of Medina. This treaty united the differing tribes of Medina into a single community, an ʾUmmah. It gave freedom of religion to the residents (including the 8 Jewish tribes), established rules for peace such as blood money payments, and established Muhammad as an arbitrator for tribal disputes. For the first time, Muhammad was in a position of relative power and importance, and an Islamic state began to form.
So in conclusion, this period could be seen as almost entirely bloodless. Indeed, Muhammad acted as an important figure in preventing tribal disputes and establishing a relatively stable, multi-religious society in Medina (but which was not to last).
From Medina to the Arabian Peninsula
Once in Medina, the tone of Islam began to change. Revealed surahs tended to be longer and entailed more obligations and punishments than mere calls to faith. This is also when other faiths began to be overtly mentioned, in particularly the People of the Book. However, Muhammad was feeling increasingly threatened by the Jewish tribes and desired to assert himself and Islam as an independent religion. Wael Hallaq posits that this was because the Jews were regarded as the guardians of monotheism. In any case, stricter rules were layed down, the direction of prayer changed for Jerusalem to Mecca, and slowly tensions grew between the Jews and the Muslims.
Around 624 Muhammad began to lead armed excursions against the Meccans. These were not wars of conversion, but rather raids against caravans. The Muslims who followed Muhammad to Medina had to leave behind many of their possessions and so the overall community was rather poor. The Battle of Badr ended up being a turning point for Islam. Despite being outnumbered 3 to 1, the Muslims handily won the battle against the Meccans, giving impetus to Muhammad’s claims that he was a prophet of God. Shortly after this battle, Muhammad expelled one of the Jewish tribes of Medina, the Banu Qaynuqa, allegedly on charges of dealing with the Meccans. Thus the first “purge” happened. It was however still rather bloodless. The battles against the Meccans were par for Arabia and the Banu Qaynuqa were not killed off. Another Jewish tribe, the Banu Nadir, was expelled later that year, after the Muslim defeat at the Battle of Uhud.
627 was the next turning point for Islam, with the Battle of the trench. The Meccans, along with the Banu Nadir, laid siege to Medina. However, they too failed. The failure of the coalition led to the slaughter of the last great Jewish tribe of Medina, the Banu Qarayza. In the first truly bloody act of Islam (although again, influenced also by economics and politics), the men of the Banu Qurayza who did not convert were beheaded and the women and children sold into slavery. This act is often brought up as “proof” that Islam has been inherently violent since its conception, but there was much more at play than religion. The Banu Qurayza were economically powerful within the city, and Muhammad had a political excuse to get rid of them following the Battle of the Trench.
In 628, the Treaty of Hudaybiyya was made between the Muslims of Medina and the polytheists of Mecca. This treaty lasted for 2 years until a tribe allied with the Meccans attacked a tribe allied with the Medina. Following the broken truce, Muhammad conquered Mecca in 630. He did destroy the shrines at the Kaʿba, however all but 10 men and women were spared and many converted. Those who were killed did so because they had openly mocked Muhammad in the past. Muhammad proceeded to rule from Mecca until his death in 632, spreading his power throughout the Arabian Peninsula.
This is the second stage of Islamic spread. It was more bloody than the first, involving several wars and the massacre of the Banu Qurazya. However, it wasn’t excessively bloody.
To the Levant and Beyond
Following Muhammad’s death in 632, he was succeeded as Caliph by Abu Bakr. Abu Bakr’s rule is characterized by the Wars of Ridda, or Wars of Apostasy. These wars were fought against Arabian tribes who claimed that their allegiance to Islam and to Mecca was given to Muhammad alone, and thus after his death they should be free of Islam and the tribute they had to pay. Abu Bakr, in launching these wars, set the precedent that de-version away from Islam was not to be tolerated. Thus the Islamic state began to act cohesively to not only spread Islam but ensure that it remained the dominant faith within its borders.
After these wars, Islam began to spread Northward. I believe this is what primarily interests you (I got a bit carried away writing the background. Sorry about that).
The conquering Arabs initially intended for Islam to be the religion of the military conquers, but for the conquered to retain their original religions. For this reason, people were not forced to convert even when militarily conquered. Instead, they had to pay that jizya, or poll tax and lived as dhimmīs, or a protected class. I’m going to quote below something I wrote up on the jizya before.
One key aspect about the early expansion of Islam is that it did not attempt to force its way of life upon other people. Under the Caliph 'Umar, it was envisioned that Islam would be for the Arabs, who would exist as a sort of military caste above the conquered people. This meant that the conquered populations were disturbed as little as possible, and conversions were only on a voluntary basis. This precedent was set with Muhammed allowing the Jews and Christians of Arabia to keep their religion if they paid the Jizya (poll tax). This payment would make a member of the religions of the book - Jews, Christians, and later Zoroastrians - members of the protected class, or dhimmi. These people would be reserved from having to pay the aforementioned Zakat tax and from military service within the empire. This isn't to say that taxes wouldn't get absurdly high though, as Ira Lapidus notes that taxes on peasants could reach upwards of 50% of the value of the goods. It does, however, mean that the Muslim invaders were not hated. In fact, some Christian tribes had allied themselves with the Muslims against the Sassanians or Byzantines.
Oddly enough, the Religions of the Book flourished in the early days of conquest with Islams coming. Many previously repressed sects were able to abound, and apocalyptic messages were numerous. This changed though as time went on. 'Umar II (r.717-720) forbade Christians to hold powerful government positions. Other successive rulers forbade minority religions to ride horses, bear weapons, or show outward religious symbols in public. Repression came in waves, as one Caliph would crack down (Such as Yazid II destroying churches and animal sculptures) and then others relent. Keep in mind through all of this that from the 7th to the 11th century, upwards of half the world's Christians lived under Islamic rule, yet they were not forced to exile or forced to convert by force (at least in large-scale).
Hitting the character limit. Finished up in a second comment