Particularly before the Ottomans, did the Christian inhabitants of Muslim states form part of the military? If not, how could the muslim government guarantee enough soldiers especially when ruling a vastly Christian population?
/u/NomadicCircle makes a good point about the presence of Christians fighting alongside Muslims in Islamic Spain (and especially post-Caliphate, during the Taifa period of largely independent principalities). One of my favorite stories from this period actually involves the Christian Kingdoms of Léon and Navarre joining forces with the Berber Almohad dynasty in 1296 in order to fight against the Kingdom of Castile. This only ended when the Pope declared a crusade. Not against the Almohads as one may expect, but against Léon! But of course, this was more Christians allying with Muslims rather than fighting within Muslim commanded armies.
Where I'd disagree slightly with /u/NomadicCircle is that Spain was the only place they could have formed part of an army. Although Christians later came to represent smaller proportions of the population, they originally were the majority in many of the conquered lands - Syria, Egypt, Palestine, etc. Egypt itself did not become majority Muslim until around the 9th to 10th century AD, roughly 200 to 300 years after conquest.
Christians were present fighting alongside some of the earliest Islamic expansions, such as the Namir and Taghlib tribes joining Islamic forces during the invasion into Southern Iraq. This was before the "medieval" period, but still showed Christians (who would later be under Islamic rule) willingly fighting alongside Muslims.
One important point I wanted to note that is that Christians were, if they payed the jizya poll tax, exempted from military service. Early Muslims, particularly under the rule of Caliph Omar II, viewed the Muslim Arabs to form a sort of conquering military class that would remain separate from the population at large (although this obviously did not last). Paying the jizya, in addition to the other rights it gave, was thus like paying for protection from the ruling Muslims. As Christians and other People of the Book were exempt from military service under this scheme, they would naturally compose a smaller percentage of the army and you would have been less likely to hear of their exploits.
Well the only place where Christians, who were numerous and were not a tiny minority, could form a part of an army was within the Islamic Spain. Here they formed special units which fought for the Caliphate in Spain much like their fellow Muslim inhabitants did. These Christians soldiers either were recruited from cities to serve as a personal guard to the Caliph/Sultan or were called up by Christian minor lords who answered the call to arms.
Islamic Spain also found its recruits throughout North Africa in particular Tunisia and Morocco where many times especially during the Umayyad Caliphate they were called to either save their territory or help capture more of them. Many later dynasties had their power base within North Africa rather than solely relying on Spain itself.
Sources: