When Mu’aawiyyah bin Abee Sufyaan was the governor of Syria, he urged ‘Umar bin al-Khattaab to campaign by sea, and told him how close the Byzantines were to Homs. He said, “In one of the villages of Homs, the people can hear the barking of their dogs and the crowing of their roosters.”
‘Umar was almost convinced, and so he wrote to ‘Amr bin al-’Aas saying, “Describe to me the sea and those who sail on it, for I am thinking about it.” ‘Amr wrote to him saying, “It is like a huge creature being ridden by a small creature; if it stays still it will scare you and if it moves it will make you lose your mind; there is no certainty about it and great doubts about it. They (sailors) are like worms on a stick; if it tilts they will drown and if it is saved you will be astonished.” When ‘Umar read the letter of ‘Amr, he wrote to Mu’aawiyyah saying, “No! By the One Who sent Muhammad with the Turth, I will never let a Muslim campaign by sea. By Allaah, a Muslim is dearer to me than all that the Byzantines have. Stop suggesting that to me.”
But the idea kept nagging at Mu’aawiyyah; he saw the Byzantines and their land, and kept hoping to conquer it. When ‘Uthmaan became the Khaleefah, he brought the matter up again and urged ‘Uthmaan to consider it. ‘Uthmaan replied by saying, “I am already aware of how ‘Umar (may Allaah have mercy upon him) responded when you asked him for permission to campaign by sea.” Then Mu’aawiyyah wrote to him again, trying to convince him that it was no major thing to travel by sea to Cyprus. ‘Uthmaan wrote back to him saying, “If you take your wife with you, then you have our permission to go, otherwise no.” ‘Uthmaan stipulated further conditions by saying, “Do not select people and do not draw lots; give them the choice, and whoever chooses to go willingly, let him go with you and help him.” When Mu’aawiyyah read the letter of ‘Uthmaan he started mobilising people to travel by sea to Cyprus. He wrote to the people on the coast ordering them to repair their ships and bring them close to the coast in Palestine at Acre, which he had refurbished so that the Muslims could travel from there to Cyprus.
[A collection of narrations taken from: Taareekh at-Tabaree 5/258-260; al-Idaarah al-'Askariyyah fid-Dawlah al-Islaamiyyah 2/538]