By plane
Most travellers take a flight to Tawau from either Kuala Lumpur IATA:KUL or Kota Kinabalu IATA:BKI, then travel overland by taxi Tawau airport to Semporna town at RM 95. First time travelers are advised to either take an airport taxi or if possible, arrange for shuttle service if one has booked for accommodation or diving packages from tour/diving operators operating in Semporna. Some of the more established ones are like Sipadan Water Village Resort (http://www.swvresort.com/...) and Uncle Chang's (http://www.ucsipadan.com/...).
By bus
From Kota Kinabalu: Direct from Inanam station to Semporna or Tawau, 8-10 hrs, 75 MYR one-way. Departs 7:30AM & 7:30PM. To get to Inanam station you can take the public bus from the long distance bus station in KK city on Jalan Padang Bus #3 to "Terminal" or "Inanam", purple bus stop, 20 min, 1.50 MYR to the Inanam bus station, or a taxi ~20 MYR. Call 088-384701 or 088-384702 to book tickets for the Dyana Bus to Semporna. Note that in high season Jun-Aug these buses fill up fast so book at least a day in advance.
From Sandakan: there are two direct buses to Semporna run by Dyana Bus at 7:30 am and 2 pm 5-6 hrs, 40 MYR. If you miss the direct bus, you can also try taking a bus to Lahad Datu at least 1:00pm, 18RM, and from there take a minibus to Semporna leaves when it's full, 24RM.
From Sepilok: Take a taxi to Sandakan and take a bus from there, or hail down the bus at Sepilok junction works if there are seats available on the bus. Taxi can be booked through your accommodation in Sepilok for ~30 MYR pp shared, and takes 1 hour.
From Kinabatangan River: Let your tour agent drop you off on a busstation or a bus stand on the main road to Semporna. There your tour guide might also help you finding a bus to Semporna: either the one heading straight to Semporna a bus passing by that left from Sandakan early in the morning or, when you missed that bus or when it is full, a minibus to Lahad Datu. From Lahad Datu you can catch another minibus to Semporna. Costs for the minibusses are about RM 20,- to Lahad Datu and RM 29,- from Lahad Datu to Semporna.