Java has good transport connections from end to end, and you rarely need to fly unless you are short on time.
Trains are the most comfortable way to travel between major cities. Two main lines run between Jakarta and Surabaya -- one via Yogyakarta and Solo, the other via Semarang. Executive-class carriages have air conditioning and assigned seats, and are worth the modest premium. In the east, trains connect to the ferry at Ketapang for Bali; in the west, to the ferry at Merak for Sumatra.
Buses are the main form of inter-city transport and range from cramped public services to comfortable air-conditioned express coaches. Small minibuses cover shorter routes and backroads. Door-to-door minibus services are surprisingly convenient for mid-range trips.
Hiring a car with a driver is affordable and far less stressful than driving yourself. Java's roads are busy and the driving style takes some getting used to -- drive on the left and yield to anything bigger than you, more or less sums it up. Motorbikes are available for hire everywhere but demand real skill in traffic. Bicycles are fine for getting around town but not practical for long distances.