My info is 4 years old, so could all be changed by now...
But at least back then, there was no ferry boat between Western Malaysia and Borneo (the travellers, who had brought bikes to Borneo from there around that time, had had to freight them in).
I believe the Tanjung Priok harbour (Jakarta), or Surabaya, should be your best options for ferries to Borneo. But finding out about when they would leave, was more than a bit challenging: for example the Pelni company, that operated many of those routes, had not updated their webpages during the last 3-4 years!
Also to get a big bike into the boat as your luggage on those longer routes could become a headache. At least Pelni´s official policy at that time was, that they do not transport motorbikes (but I didn´t get to actually test, if that was really so).
Last edited by pecha72; 2 Feb 2012 at 06:26.