best way to travel to Okinawa?

After a great trip last year, I decided to go to Japan again for 3 weeks. This time I'd like to put okinawa and the surrounding islands on my itinary.
As far as I can see there are 2 ways of getting to okinawa:
By boat is the first and cheapest option. However, from Kagoshima this will be a journey of over 20 hours (one way, I have to get back too), and I have no clue how comfortable these boats are. Getting to Kagoshima is no problem, as I will posess a railpass.
The other -obvious- option is by plane, but this seems too expensive: prices of almost 300 euro for a single flight, and I'd have to book a return as well.

Can anyone tell me what the most practical/economical way is of travelling to okinawa?

I would go for plane; it may seem expensive, but having in count that boats take so looong I wouldn�Lt be looking that much to the plane price.

Try Skymark, http://www.skymark.co.jp/en/index.html

They have fares as low as 10,000 yen.

Or you could try the Welcome to Japan fares with ANA or JAL. These fares, depending on the airline you come in on can be as low as 10,000 yen or as high as 13,650 yen.

ANA: http://www.ana.co.jp/wws/us/e/travelservice/reservations/spe...

JAL: http://www.jal.co.jp/yokosojapan/

great help!
I looked at skymark before, but I couldn't find okinawa on their available routes...but ofcourse Okinawa airport = Naha airport *slaps forehead*
In any case, this was exactly what I needed, thanks :)

Not really a Japan-related question, but..so far I've only booked flighttickets trough a travel-agent. If I order them on the site, does that mean I just pay them by CC and pick them up in a few months when I'm in Tokyo?

I haven't booked with them yet, but I would assume that they would be e-tickets. Just bring your receipt to the ticket counter and they will give you your boarding pass at that time.

Yes you buy online, show up at the airport the day you fly and get a boarding pass. They are e-tickets so no need for actual paper tickets.