There are multiple daily flights from Honolulu on Pacific Wings for $29 each way or on IslandAir. Pacific Air's primary aircraft is a 9 passenger, 1 engine Cessna Caravan. Seats on Island Air range from $30 on up.
Inexpensive flights also available from Maui (OGG) via Pacific Wings and Mokulele. Round trip should cost around $120. If you get sea sick (the ferry is okay at best in the morning, takes 90 minutes each direction, but usually awful in the afternoon.) then flying is a great option. Amazing sights, no TSA, show up 20 minutes before and head out with a handful of other adventurers or commuters (remember to head to the commuter terminal!). Pilots are all fresh air-force cadets and are super fun to hang out with. The views are incredible and cannot be seen from the water. Worth the extra cost!
Many of the sights and beaches are spread out across the island so a car or tourbus is the best way to get around. There is an Alamo rental car location at the airport. They only have van's and Jeeps (as of Oct. 2012.) Our Jeep was $85 for the day. Gas is fairly expensive too, so remember to drive with aloha :-) Roads are in very good shape around the island.
For shorter distances, mules and horses are another option.
Molokai Car Rental 866-344-7612 [http://www.molokairentalcar.com Molokai Car Rental] Molokai car rental rates and information. Molokai airport location MKK Hoolehua, HI 96729.
Kalaupapa National Historical Park - Visits to the former leper colony (still home to a handful of former patients who chose to remain there) are only possible as part of a tour, such as .
Molokai Museum and Cultural Center, Kalae Hwy, Kualapuu, ☎ +1 808 567-6436. edit. An old Sugar Mill that was restored. Lot's of history. Worth the $5 admission, $1 for students!
Phallic Rock, exactly what it sounds like. Short hike from parking lot at Pala'au State Park. Make sure you also stop at the Kalaupapa look out at the same trailhead. amazing views.[]
Kapuaiwa Coconut Grove, Highway 460 about 1.5 miles (2.4 km) east of Kaunakakai. Right across from the row of churches.
Churches built by Saint Damien Drive out to Halawa valley and you will pass two in excellent condition not too far from kaunakakai. Continue this road to the very end for AMAZING sights. The road is great but is one lane for most of the second half.
Go to the west end of the Island to see the three mile white sand beach called Papohaku. Guarenteed you will not see more than a handful of other people there. Good to walk on, no swimming. Harsh surf. Go to Maunaloa. It was part of an old plantation and is neat to see. It has a kite factory!.
Drive the East side of the island for a pretty crazy road. Amazing sights but drive slow, don't ride the brakes and take pictures!
Kualapuu cookhouse, 1700 Farrington Avenue Kualapuu, HI 96757, ☎ (808) 567-9655. edit Amazing meals for breakfast, lunch and dinner. Lots of locals say it is the best.
Paddlers Inn, 10 Mohala Street Kaunakakai, HI 96748, ☎ (808) 553-3300. edit. Some say is is the only good place to eat in Kaunakakai. It looks a bit rough to some (like a party place) but the staff was friendly and the food was great!
There are also many other places in Kaunakakai such as their Pizza company, hamburger drive-in joint, and a Subway.
Kaluakoi Villas, 1121 Kaluakoi Rd, ☎ +1 808 552-2721, . Stay at Molokai's popular Kaluakoi Villas located on the west end of the island. Featuring great amenities including the Kaluakoi Golf Course.edit
Aqua Hotel Molokai, 1300 Kamehameha V Hwy, Kaunakakai, ☎ +1 808 553-5347, . Features open-air, oceanfront bungalows located on Kamiloloa Beach, adjacent to Hawaii's only barrier reef. Pet friendly suites are available. Amenities offered include a swimming pool, an oceanfront restaurant and on-site spa facilities.edit
Hotel Molokai, 1300 Kamehameha V Highway, Kaunakakai, HI, 96748, ☎ 808.553.5347, . Cute little villas that are SO neat. Their kitchen burned down (June 2012) and will be rebuilt soon. I would come back and stay here in a heartbeat.edit