Islam first came to the Philippines in the late 1200s, introduced by Muslim merchants and Sufis by way of Indonesia. Over the next couple of centuries, the religion spread among the indigenous people of the islands, moving from Borneo through the Sulu archipelago. By the 1400s, it reached Mindanao. By this time, political institutions had developed and during the fifteenth century, sultanates were established in the southern islands.
In the 1500s, the Spanish arrived and established colonies in the northern islands. For the next 350 years, the sultanates and the Muslim people of the southern islands (named "Moros" by the Spanish after the Moors (Andalusian Muslims) who had recently been expelled from Spain; they have recently adopted the name Bangsamoros for themselves) fought against the Spanish. The Spanish Christianized the indigenous people of the northern islands, who were called Indios. As part of this process, the Spanish often depicted the Moros to the Indios as dangerous or inferior so that the Indios would side with the Spanish against the Moros.
Despite the technological superiority of the Spanish, the Muslim sultanates, though greatly weakened, were still independent of Spanish rule even in the 1890s. At the end of the Spanish-American war in 1898, Spain ceded its Philippine colonies, along with other possessions, to the United States. The U.S. signed a non-interference treaty with the sultanates. However, the United States then proceeded to establish a colonial administration over both the Indios and the Moros, desiring to integrate them into a single nation.
The Philippines gained independence from the U.S. in 1946 (after enduring occupation by Japan during World War Two). The leaders of the Philippines then pursued a policy of settling Christians in Mindanao and concentrating land ownership in their hands. Muslims now form a minority in Mindanao and are economically and culturally marginalized by discriminatory policies that favor Christian Filipinos.
Mindanao and the Sulu archipelago were not part of "the Philippines" until 1900. They formed a nation that was separate historically, culturally, and religiously and which enjoyed an independent history going back over six centuries. In the last hundred years, they have been forced to assimilate into the Christian Filipino (Indio) national identity, and been gradually but systematically dispossessed and supplanted in their own land (this seems similar to China's policy in Tibet and the less well-known Xinjiang).
This is the context in which we need to understand the Mindanao and Moro independence movements. As with the Chechens, the Kashmiris, and the Palestinians, the Moros consider themselves to be fighting a legitimate national liberation struggle against an occupying power. This isn't some simplistic story in which evil Islamic fundamentalists decide to commit terrorism against an innocent Christian people for no reason. Terrorism in Mindanao, as in Chechnya, Kashmir, and Palestine, occurs when extremists hijack a cause and use immoral tactics to further their aims.
If we are to resolve the problems in Mindanao (and in Chechnya, Kashmir, and Palestine) we need to look beyond simplistic stories and examine the genuine grievances people have and the genuine oppression they face that makes them willing to engage in armed resistance and to listen to the words and tactics of extremists. Establishing justice is the best way to bring about peace. Further violence and repression will only make things worse. One would think that this would be obvious by now.
Here is some reading about the Moros of the Philippines to back up what I've said here and to provide you with further information. Mindanao: A Place of History, Culture, Beauty, and Conflict provides historical background and essays. In Moro-Christian Co-Existence and Conflict in the Philippines a Catholic scholar looks at the religious aspects to the conflict. Mindanao: The Hazy Shade of Peace in the Philippines examines the various Mindanao and Moro independence movements and their history. Fire in Mindanao, also by a Catholic scholar, looks at these movements in more detail and discusses the prospects for peace. Amnesty International reports on human rights violations by the Philippine government and army in their campaign to put down the Moro rebellion. The Sultanate of the Philippines (Google cache) focuses on the notorious Abu Sayyaf hirabists (a Islamic term for bandits and terrorists, which Abu Sayyaf most definitely are both of). Understanding Bangsamoro independence as a mode of self-determination argues that a free Mindanao will be a peaceful Mindanao.
As a bonus, learn about Sitti Kabira, the woman who in the late 1600s became ruler of the Sulu sultanate (according to Forgotten Queens of Islam, the sultanate of Aceh in Indonesia was also ruled by a woman at this time, Safiyyat ad-Din).
Note: Some broken links removed 7/31/04