Interesting subject. We know that the first Muslim community in Indonesia first appeared around the 12th century yet trade with Arabs had already started in the 8th century. Apparently it took from the 12th to the 16th century for Islam to become the major religion of Indonesia.
Obviously, Islam only spread through means of trade but it's still quite interesting to see how it caught on so well. As far as I know, maritime and especially island dwelling peoples tend to be quite tolerant towards foreign ideologies. But then that's not enough as an explanation.
I think that many of the Arab traders must have settled in Indonesia and married with influencial people. If a ruler was Muslim, then it would make sense that the population felt inclined to convert and also, as far as I know there was no religious opression caused by this difference.
a little bit more on the subject
http://en.wikipedia.org/wiki/Islam_in_Indonesia