I arrived Tawau airport at about 8pm and I took a fixed rate taxi from airport to Semporna fro RM95 (Oct 08). See more pic for taxi receipt. There are taci to Tawau city and other places. The journey to Semporna is about 1-1.5 hours, depending how fast the driver drives. My trip was less than 1 hour.
There are daily bus from Semporna to Sandakan and to KK. 1 bus to Sandakan departing 7:30am for RM40 (Oct 08) and the journey time is about 4-5 hours. Bus to KK departing 7:30 am and &:30pm for RM 75 (Oct 08) and journey time is about 9 hours.
There are two bus companies going for KK at same price. See 2nd pic for the executive coach. company Dyana.