Train

I think by far Plane is the efficient way to travel in Indonesia.
However, while you're in Java it will be to much to travel by plane.
I prefer train! Yes.. train!

The only train operator in Indonesia is PT Kereta Api - http://www.infoka.kereta-api.com

The network was originally built by the Dutch & Java by far has the best railway network, with trains connecting the capital city of Jakarta with other main cities, i.e. Surabaya both via Semarang on the north coast and via Yogyakarta and Solo through the southern main line.

Normally, there are 3 (three) class of service:
1. Eksekutif class (Soft Seater with Air Con + Meals)
2. Bisnis class (Soft Seater non Air Con & No Meals)
3. Ekonomi classes are also available for the more budget-conscious traveler, but comfort and safety are noticeably less (due to congestion and length of travel time).

No sleeping car service is provided in Indonesia, and the best accommodation provided is air-conditioned, adjustable reclining seats in the Argo and other eksekutif class trains.

Ticket reservations can be made one month in advance, although generally tickets will still be available almost to the last minute. An exception is the very busy Lebaran season, during which time it is not advisable to travel due to the extremely high demand for tickets.

By the time I'm writing, I only found 1 (one) website that serve online train reservation. You could try to go to http://www.javatourism.com/catalog/index.php?cPath=40