From Kota Bharu there is a direct local bus service (City Liner) (RM 6, 1.5h). It's also easy to arrange a share taxi ride RM80.00- virtually any guesthouse or hotel in Kota Bharu will organise this.
From Kuala Terengganu take any northbound bus and get off at Jerteh (110km). Continue from there another 17km by local bus, taxi (10-20RM/car) or walk to Kuala Besut jetty.
From Penang east-bound Mutiara Ekspress depart from Sungai Nibong ekspres bas (express bus) terminal (public bus 401 from Penang Jetty RM2) to Jerteh via Kota Bharu twice daily (9AM/PM, RM46), sometimes to Kuala Besut depending on number of passengers going there. The journey requires around 6 hours. There is no direct bus from Butterworth to Kuala Besut! From Butterworth you can take two direct buses (Mutiara at 10PM and S.P.Bumi 9AM/PM) to Jerteh (RM42.70 vs RM42.00) and from there take local bus (?RM), taxi (10-20RM/car), walk (flat well signed road :-)) or hitchike for another 17km to Kuala Besut Jetty. You will arrive to Jerteh at 3-5AM at Petrol station next to T junction of roads to Kuala Besut and Terengganu in middle of nowhere, so you will have plenty of time bargain with taxi drivers who are waiting there for you or for walk to bus station in Jerteh (1km on main road). Easiest way from Penang to Perhentian is take GSM (Persada) direct bus which is departing from Komtar building in George town (in walking distance from tourist area Lebuh Chulia) directly to Kuala Besut jetty, where you will just walk few minutes to boat (1st you have to wait couple hours in travel agency because 1st boat departs at 8AM and you will arrive there around 4:30AM, so you can buy speedboat ticket at any of agencies for fixed price 70RM/return if you don't have one already). Bus from Butterworth to Kota Bharu cost RM35 (many companies/departures, fixed cartel price) and from there it's only 50km (90min) to Kuala Besut by direct local bus (6RM).
Alternatively, you can go to Prangin Mall and ask any bus counter for a ticket to Kota Bharu (RM37 or RM38). When you arrive at Kota Bharu Bus Terminal. From KB Bus terminal, follow directions under "from Kota Bharu" above.
From Kuala Lumpur there are only 2 buses services going direct to Kuala Besut, namely Mutiara and Mahligai. The cost is usually RM40.00, and they drop you off within walking distance of the jetty. The buses leave twice daily, 9am and 9pm and arrive in Kuala Besut around 5am. The first boat is at 8AM (until then is pier gate closed!). Mutiara and Mahligai buses usually stop near the jetty. The trip is about 9 hours with only one stop at around 1am/pm.
Taxi drivers may try to take you to a travel agent of their choosing, who will pay them commission (which gets charged to you). If you are going to the Perhentian Islands and already have accommodation booked, just go directly to the jetty, or pick an agent of your own choice, but in the end you will pay 70RM for return ticket everywhere so it really doesn't matter which travel agency you will choose.
Yaudin guesthouse - RM20/night - Cheap but very bad quality with holes in the bed sheets and lots of mosquitos or bed bugs. Better off getting into Kuala Besut early enough to go straight to the islands.