This question came to me while playing Crusader Kings II when I learned that Muslim dynasties had an open succession law where the most powerful son of the head of the dynasty becomes heir to all titles. This is ostensibly based on Ottoman succession law, but I have a heard time believing this was standard throughout the Muslim world. For one thing, the Turks were new comers to the Middle East and likely brought their own succession laws with them. It is possible Arab dynasties might have adopted this method after the Turks moved in, but the Umayyads in 876? I don't think so. So how did the various dynasties decide succession? I know there are several, but I'm more interested in the most famous ones - the Ummayads, the Abbasids, and the Fatimids.
Muhammad's death in AD 632 threw the Islamic world into a political crisis. Muhammad had not specified who should succeed him. And in fact, Muhammad had taught that he was to be the final prophet. The question of whether Muhammad should even be succeeded was likely considered. Muhammad had also been the glue holding rival factions together. The ansar (converts from Medina) and muhajirun (Meccan converts), along with converts from among the Quraysh and Thaqif, still considered themselves to be political rivals, and after Muhammad died the ansar wanted to choose a chief for themselves and encouraged the muhajirun to do the same. Ultimately, a meeting of all parties was arranged and the muhajirun argued persuasively for Abu Bakr to lead a united Islamic state. Umar al-Khattab stood up and dramatically swore allegiance to Abu Bakr, and so the Prophet's most loyal companion was selected as khalifa, successor.
While still alive, Abu Bakr chose Umar as his successor, despite protests from prominent voices among the ruling elite. Umar would be assassinated, and his successor, Uthman ibn Affan, was chosen by a small group of Quraysh. Uthman would select only men of the Quraysh clan as provincial governors. This angered many from Medina and other areas of the empire who opposed Meccan dominance, and this led to his murder.
Ali would be the fourth caliph, but only for a short time. Civil war broke out between his supporters and kin of Uthman and others who were against his election. He was assassinated in Kufa.
The first four caliphs are called the Rashidun, or rightly guided. But they set no clear precedent when it came to who should succeed a Caliph.
After Ali, Mu'awiya came to power, and from that point on "the position was virtually hereditary."
sources:
Early Islamic Conquests, Fred McGraw Donner
A History of the Arab Peoples, Albert Hourani