I highly recommend Alex Metcalfe's The Muslims of Medieval Italy. He covers the whole time period of Muslim residence on the island, even setting the stage in the context of the politics of North Africa.

Since the questions you're asking are so sweeping and so smart ("What evidence do we have for this"), I honestly think you'll do better with the book than with an AH answer.

~~

But for the briefest overview:

We have very, very few sources for the Islamic era of Sicily, and most of them are Christian or Jewish, and originate outside Sicily. That state has to do with the multiple cultural near-annihilations. Muslims nearly obliterate Byzantine culture, except for a few Greek communities in the northeast. Latin Christians allow Muslim communities to continue as Muslim for quite awhile, but eventually deport the entire Muslim population to mainland Italy. However, there are a few less direct elements--surviving Greek churches that were turned into mosques. And more impressively, Muslims turned Palermo from a middling city into one of the most important trade and cultural centers of the Mediterranean.

Population is harder to trace. It seems that one of the reasons the Aghlabids wanted Sicily in the first place was as a source for slaves. We also know that the Greek ecclesiastical hierarchy, including monks, fled once they realized the Byzantines were going to lose. But then external sources claim the island was essentially deserted until the 900s, when North African Muslims began to move in. Metcalfe seems a little skeptical of this, but admits he can't really say for sure either way.

The religious balance starts to shift a little in the 1020s, when Normans start to arrive...as settlers. And not just in the remaining Greek Christian areas, either! Some of them even serve in the various Muslim armies--yes, armies plural. Like Spain, Sicily's conquest by Latins was greatly aided by relative anarchy and infighting among Muslim lords.

Upon the various stages of Norman conquest, there were no efforts at mass conversion. This was because [1] it was more profitable to make Muslims pay extra taxes (not a replication of the dhimmi system, though; the Normans created their own) [2] the Normans were worried about rebellion if they tried [3] a couple of high-profile attempts went very badly.

A lot of Muslims did emigrate. They went to al-Andalus (Iberia) and North Africa, but not really to the Near East. However, enough stayed behind that the communities had leaders who were powerful enough to form almost-alliances with, or at least secure special privileges from, various Norman rulers.

In the 1100s, one of the big deals is that ostensibly "Christian," but for all practical purposes still Muslim, officials serve in the Latin government. Jeremy Johns showed that it's not actually a carryover from earlier Aghlabid/Kalbid bureaucracy, but the Rogers Et Al. trying to copy the Fatimid Egypt bureaucracy (prestige + functionality).

The late 12th century sees increasing marginalization of Muslims, and a decline in the special privileges/protection granted to their communities. (This has a lot to do with Norman politics). Still, Muslims don't seem to convert to Christianity in large numbers.

In the mid-13th century, though, Islamic Sicily came to a harsh end: Frederick II deported the entire Muslim population to Lucera, on the Italian mainland. (He did it for mostly economic reasons, but this was very bad for Sicily--it basically collapsed its agricultural economy entirely). The now-Lucerans did set up a fairly thriving "colony," despite labor, army, and tax requirements. But even this couldn't last: in 1300, Angevin ruler Charles II brutally suppressed the colony, selling its residents into slavery.

~~

...So really, I recommend reading Metcalfe. There is just SO MUCH THERE!