The difficulty is that nowadays people definitely fly to Okinawa, so people who take ferries to Okinawa are only those who need to travel with their cars, with no time restriction, and maybe someone who want to travel from one Okinawa island to another. From Kagoshima (southern tip of Kyushu island) to Naha, there is a ferry that takes you to Naha, but ony 7, 8 times in a month, and it costs at least 14,200 yen one way (no sleeper), AND it takes 26 hours.
If you fly from Fukuoka to Naha, that would be under 2 hours, and regular airticket costs 20,000 yen or so. Discount ticket available as Uji suggested.
I could not find any English information on the ferries:
http://www.aline-ferry.com/route/kagoshima-okinawa.html