Although there's no real consensus on how or why the first Normans arrived in Southern Italy, by 1042 they were a sufficient ethnic and military presence that Duke Guaimario of Salerno approved the Norman mercenary William of Hauteville's plan to seize Sicily.

The Normans, perhaps as a semi-conscious hark to their Viking forefathers, were particularly predisposed to offer their services as bodyguards for people traveling to and from the Holy Land, even long before the crusades. These early travelers would be a tickle of clergymen and the most pious nobility, but it's nonetheless an interesting precedent. These Normans invariably returned by passing through the southern half of Italy, and found the Principality of Salerno (a rump-state of the defunct Kingdom of Lombardy) and a couple of splinter Duchies locked in systemic conflict with both the Byzantine Empire and the Abbasid Caliphate. Soon, a small clique around four Norman brothers, with retinues that could be as small as thirty followers (at least according to the Byzantine chronicler Anna Comnenos) entered the permanent service of Guaimario, the Prince of Salerno. Before long, ethnic Normans were a leading component of the Salernitan armed forces, contributing to the stabilization of Guaimario's borders. The Norman leaders, brothers William, Roger, Drogo, and Robert, all from the town of Hauteville, went on to carve for themselves a semi-autonomous fief in the Italian region of Puglia, which they had seized from the Byzantine Empire. Prince Guaimario was more than happy to let their small polity exist in exchange for their continued military support. And when in 1047 Guaimario was assassinated in a plot by a particularly rambunctious subject, it would be the Normans in Puglia to rush to Salerno in force in order to place Guaimario's son Gisulfo on the throne, and neutralize the conspirators' proposed usurper.

The events after Guimario's death proved that by the early 11th century the Normans were integral to Salerno's stability and strength. Indeed, not only would they undermine the usurpation plot, they would go on to plan and carry out a campaign to expel the Byzantines from the province of Calabria. Indeed, so integral would they be to the Salernitan polity that the new Prince Gisulfo would soon develop a feeling they were getting too powerful and cool his attitude towards them, attempting to isolate them politically. All would come to a head in 1053, when Gisulfo struck an alliance with the emergent Papal States to the north in order to organize a punitive expedition against the Hauteville's main power base in Puglia. The outcome was a resounding defeat, causing Gisulfo to retrench himself in his capital. By 1076 the Normans had removed Gisulfo from power altogether.

After having consolidated control in Salerno, the four Norman brothers would go on to conquer the whole of Sicily, paving the way for one of their descendants to be crowned King and complete their dramatic ascendance.

So rather than an outright conquest, it's more correct to say Normans fundamentally integrated themselves in the martial/land-based political hierarchy in Southern Italy. Without diminishing the astounding military achievements of individuals, it is nonetheless true that first they built a social and economic power base for themselves, and only in a second moment neutralized the disunited and dysfunctional local political class. Indeed, Prince Guaimario's vitality and effective ruling style, which must have played no small part in convincing the last and most numerous wave of Norman adventurers to stay and fight in the South, was most certainly the exception rather than the rule. The prosperous, commercially vibrant, and agriculturally fertile states in Southern Italy had long been politically isolated and had became inward looking to the point of being beset by dysfunction and endemic separatism. Perhaps, then, this sort of upheaval was inevitable: after all guile and subterfuge had been the hallmarks of the continued political autonomy in Southern Italy since the time of Charlemagne in the eighth century. Indeed, Duke Arechi of Benevento, a powerful and fiercely loyal vassal of the King of Italy recently deposed by the Frankish Emperor, had sent his son Grimolado as a hostage to Charlemagne's court in exchange of the right to continue ruling, but upon his return Grimolado immediately began strengthening the fortifications at Benevento and Salerno and began taking steps to affirm his autonomy. With such a cunning and defiant leadership, it is unsurprising that by the next century infighting would split Southern Italy in three, between Duchy of Benevento, the Duchy of Salerno, and the Republic of Amalfi. That's without mentioning Calabria and Puglia, which would remain Byzantine Military Provinces (called Thema) up to the period of the Norman conquest.

This in such a picture of institutional instability, is it at all surprising that a powerful military-governing class with foreign origins emerged? Indeed, although the leadership of this "conquest" was mostly composed of Normans, there are some key differences between this and the more familiar (to anglophone readers at least) Norman conquest of England: numerous adventurers from all over the Mediterranean populated the ranks of the Hauteville's usurpation, and these adventurers would flank, integrate themselves, and eventually replace the local governing class. Privileged administrative positions, as well as generous grants of land, were given to Normans, Provençals, and Lombards, immigrants all (more or less in that order of preference). But tensions between the existing Sicilian Greeks and these new "Latins" were easily overcome by professing adherence to the Church of Rome, only recently (in 1054) irreparably separated from the Church of the East in Constantinople. Indeed, in Sicily the Greek Christians had in great part welcomed the Normans, and played a key role in mediating between the upper class of Latin lords and the subject populations of Muslim serfs. It's interesting to note how within a generation of the Norman conquest, parish censuses show how serfs whose parents have Arabic names take Greek names; a testament to the dominant "Greek Christian" culture in spite of the new Norman ruling class and the almost entirely Arab administrative bureaucracy, and more importantly, the key role of Greek Churchmen in converting the Muslim segments of the population to Christianity.

If you'd like to read more about the Normans in Southern Italy, John Julius Norwich (my absolute favorite italianist-by-way-of-byzantiuim) wrote a history in two parts, titled The Other Conquest and The Kingdom in the Sun respectively.