*Last updated March 15th, 2018
Intercity travel can be quite expensive in Japan.
Using the extensive network of bullet trains (Shinkansen) is the easiest and fastest way to travel, as services are frequent and don't require a check-in process like airplanes. However, the costs are not small - a one-way ticket from Tokyo to Osaka will cost a little under 15,000 yen.
Use of airplanes could be suitable for destinations further away. Trains have the edge in both costs and time if you are headed from Tokyo for Sendai, Kanazawa, and Osaka. For Okayama (with the connection to the art museums in Naoshima), it's a close call and some travellers prefer flying.
If you are going further such as Hiroshima and Fukuoka, taking a flight will save you much more time.
JAL and ANA used to dominate the scene and the arrival of the low-cost carriers was rather late; it's only in the last few years that they have gotten consideration as possible choice of the travel plans for the Japanese. Most of the carriers use Narita as their base (they rarely use the more convenient Haneda) and are known for delays and even cancellations as they try to operate with the minimum amount of fleet - they are no different from the LCC's seen elsewhere in the world.
Jetstar flies to Sapporo, Kansai, Okinawa and they have also boosted the amount of services to the smaller airports in Kyushu, such as Matsuyama, Takamatsu, Miyazaki and Kagoshima; cities that previously did not have LCC's. Vanilla Air, operating under the support from major carrier ANA, has destinations like Hakodate and Amami Oshima Island, apart from the usual destinations like Okinawa and Sapporo. Peach Aviation operates mainly from their hub airport in Kansai. The only other city with connections from Narita is Fukuoka. Airasia's first attempt in the Japanese market failed, but they have returned on a much scaled-back basis, with daily flights between Centrair (Chubu) Airport of Nagoya and Sapporo.
"Highway Buses" can be a much cheaper alternative to the trains and flights. It's highly unlikely that the driver will speak English, and usually reservations are necessary - you cannot simply hop on the bus, at least for those traveling long distances.
JR operates a super-express bus that connects Tokyo Station with Nagoya in five hours. It might be more than three times the duration on a Shinkansen ride, but the fare can be as low as 3,000 yen if you are travelling on a weekday with advance reservations. However they lack any English website, so you might have to show up at the ticket office on the Yaesu south side of Tokyo station to claim your tickets in advance.
Willer Travel runs services to all parts of Japan (including some that run during the night, which would save some accommodation costs too) mostly from new bus terminal "Busta" adjacent to Shinjuku Station. You might be able to find a deal to Kyoto or Osaka for around 4,000 yen, if you can endure the long hours in a cramped space. The overnight buses have compartments for luggage, and the drivers will be courteous in helping with the storage.
Willer also runs the website Japan Bus Lines where it is possible to book routes operated by other companies with the exception of the JR buses. Most lines begin accepting reservations a month before travel.
All buses will make a 15-20 minute stop at a parking area roughly every 2 hours, as regular breaks for drivers is now mandatory under the new safety guidelines. Most drivers will set up a board with the departure time written down, so non-Japanese speakers can also understand when the buses will leave.
The major operators generally have no safety issues, but smaller companies sometimes seem to sacrifice their safety standards to allow for lower rates. Non-Japanese readers probably won't bump into them anyways as they rarely have any English websites, but it is advisable to stick with the bigger companies such as JR or Willer.
Where the buses depart from:
Most of the long-distance buses depart from either the new terminal in Shinjuku or on the Yaesu side of Tokyo Station. However the location can vary depending on the operator, so it is always important to check in advance!
The terminal opened in 2016 next to the south exit of the Shinjuku Station. There is a waiting area, a Family Mart and restrooms in the departure area on the fourth floor. This is where many of the services headed to Lake Kawaguchi, Matsumoto and Takayama depart from. There are also frequent departures for both Haneda and Narita Airport. There is a counter with English-speaking staff in case you need assistance with getting tickets or figuring out where your bus will be leaving.
Previously, bus departures from Shinjuku were scattered throughout different areas of the station but they have all been consolidated here. Old publications may still mention the existence of a Keio or Willer terminal on the west side of Shinjuku but this has closed down.
TOKYO STATION, YAESU SIDE
Many of the JR-operated buses depart from the terminal just outside the Yaesu Exit on the eastern side of Tokyo Station. This is where buses for Shizuoka and Nagoya depart from, and there are also services to both Hakone and Lake Kawaguchi from here as well. There is a ticket counter and also automated ticket machines in case you haven't made a reservation yet. The waiting room is small but you can also use the facilities of Tokyo Station which is almost like a huge shopping mall.
KAJIBASHI TERMINAL, TOKYO YAESU SOUTH
Many of the smaller privately-run companies use the Kajibashi Terminal which is about 5 minutes walking south of Tokyo Station. There is very little space to wait for the buses and for non-Japanese speakers it may be a challenge to determine where your bus is leaving from, as there are multiple berths with buses continuously going in and out.
Overnight Trains hardly exist anymore...
The country used to have a very extensive service of overnight trains, but now only one regular service remains.
The Sunrise Express runs between Tokyo and Izumo-shi/Takamatsu everyday. The trains split at Okayama, with half the trains going to the Sea of Japan side, while the other crosses the Seto Bridge for Takamatsu, Shikoku Island's largest city.
There are private rooms for one or two people and showers available, but the trains do not have a dining car.
Tokyo used to have multiple ferry links to Hokkaido and Shikoku, but now only one remain. Ocean Tokyu Ferry operates a daily service leaving the Tokyo Ferry Terminal (South of the Tokyo Big Site convention hall, no public transportation) at 7:30pm Monday-Saturday or 6pm on Sundays and arriving the following afternoon in Tokushima, Shikoku. The ships are all new and really comfortable, but does not come with a restaurant. You either bring them into the ship yourself or buy it from the vending machines!
The direct link to Hokkaido has been discontinued for quite some time, so you will have to travel to the Port of Oarai which is at least 2.5 hours from central Tokyo. From there, MOL Ferry operates two services a day that will take a grand total of 19 hours to the Port of Tomakomai. From there, it is roughly an hour to Sapporo, the biggest town. With plane tickets that are available from 3,000 yen, choosing to travel via the sea is no longer a cost-saving solution.