Getting to Japan
AIR
By far the most popular method. Most flights to Japan arrive at either New Tokyo International Airport (Narita) or Kansai International Airport: a smattering of odd flights use Fukuoka Airport, Chubu International Airport, New Chitose Airport, and (if you're coming from South Korea) Tokyo International Airport.
No matter where you're coming from, plane tickets to Japan are expensive: generally $100-$200 more than flights to South Korea. For some travelers, it's cheaper to buy a ticket to Seoul and then hop over to Japan from there: YMMV, but do try it out.
Customs officials are pretty nice for the most part, but if you're caught with any drugs whatsoever, you'll be sent to jail, no questions asked. This happened to Paul McCartney: don't let it happen to you.
When you arrive in Narita or Kansai, you might have the impulse to hail a taxi to take you to the city. Don't do this unless you're planning on splitting the fare among five or six people: you'll be lucky if you walk away paying less than ¥10,000 for the ride. Instead, stick to trains and buses for your ground transportation. More on that later.
SEA
There are ferries that run between Japan and several other Asian cities, including Shanghai, Tianjin, Busan, and Kaohsiung. I have no personal experience with these, but if you're planning on integrating Japan into a pan-Asian tour, they may spice up your travel plans.
Most ferries are overnight trips: the only really fast one is the hydrofoil from Busan to Fukuoka, which takes three hours and costs about $120 each way. Ferries from China cost about $200.
TRAIN
Some very adventurous travelers take the Trans-Siberian Railroad to Vladivostok and then fly to Japan, or take the Trans-Mongolia Railroad to Shanghai and hit the ferry. This is cheap if you don't mind sitting upright for a week, but takes a long time, and the visas can be killer.
Getting Around the City
FOOT
Some cities, like Kyoto, are best experienced on foot. Your best bet is to wangle a walking map from a Japanese consulate or tourist board, or ask the concierge at your hotel. If you read Japanese, you can find a wide variety of pocket-sized street maps at most book agents.
BICYCLE
Touristy cities like Kyoto and Nara will let you rent bicycles on an hourly or daily basis, usually for fairly reasonable rates. Don't worry about a lock: everyone in Japan has a bike, and whenever you go to a train station or office building, you'll find row upon row of unlocked bicycles.
TRAIN
In Tokyo and Osaka, you can go just about anywhere on the trains: in other major cities, the train networks are less developed but still generally useful.
Almost all train lines charge variable fares based on how far you ride. Usually, there's a map before you board that tells you the fare to your destination, and you then buy a ticket for the equivalent amount from a machine.
If you can't read the map, the easiest thing to do is buy the cheapest ticket you can get, and then show it to one of the station personnel when you get off. They will upgrade the ticket for you and tell you how much you have to pay. Sometimes, they'll even do this on the train.
Most trains in major cities have automated announcements and in-car displays in both Japanese and English, so they're very easy to use for first-time visitors and come with this noder's recommendation. Many cities offer day and week passes, which can save you a bucket of money.
BUS
City buses in Japan take some getting used to. You board in the back, and take a ticket. As the bus goes along its route, fares are updated on a screen at the front, so the longer you ride, the more you pay. Usually, the ticket is marked with a numbered zone, so all you have to do is locate the zone number on the screen to figure out how much you need to pay.
Buses are almost never in English. You have been warned.
TAXI
Taxis are quite expensive (New York City levels or higher), although you don't have to tip the driver, so it's not as bad as it might seem. On the flip side, most taxis are very comfortable, and have a doily over the seatback.
Hailing a cab is the same procedure as you're probably used to: raise your hand as it comes close, and hope it's not in use (there will be a red light if it's free, and a green light if it's occupied).
The big disadvantage to taxis is that you have to explicitly tell the driver where to go. If you just give them an address or the name of a minor hotel, they'll have absolutely no clue where to take you, and the meter will run up as they check their street atlas. Usually, the best thing to do is to have them take you to a train station or other big landmark, and then tell them where to turn from there.
CAR
You'll need an international driver's license to drive in Japan (and if you're planning on staying for more than a year, you'll need to eventually get a Japanese license). Renting a car is not impossible, and it can actually be economical if you're travelling with a sizable group of people.
Some points to consider: Driving is on the left. Most streets are ridiculously narrow, signage is almost never in English, and pedestrians always have the right of way. Expressways almost universally charge hefty tolls, and gas prices are astronomical. In short, if you're used to American driving, Japanese driving will probably kill you. Europeans may fare slightly better.
Getting from City to City
AIR
Japan has two main domestic airlines: Japan Airlines and All Nippon Airways. If you're flying between major cities, the main difference between the two is in scheduling and in where you can spend your frequent flyer miles later.
If you're traveling to Hokkaido or Okinawa, air is the only real way to go unless you prefer a ferry. Otherwise, airplane tickets are usually slightly cheaper than train tickets, and slightly more expensive than bus tickets. Usually, though, you'll need to factor in getting to and from the airport (often quite expensive and time-consuming in itself), and check-in time when you get there. In Tokyo and Osaka, you can use city air terminals to make the process quicker.
Students under 25 can get a special pass called "Skymate," which lets you fly standby on both airlines for half price. The pass costs ¥2000 and usually pays for itself the first time you use it: it's good for something like 7 years. You can get one from either of the airlines' ticket counters.
liontamer has also told me that JAL and ANA both offer one-way tickets for ¥10,000 to anywhere in Japan, provided that you fly within a week of your birthday. Fascinating!
Fares are printed in the timetables for each airline, and you can find timetables at any travel agent in Japan. If you buy your ticket a week in advance and fly in the morning or at night, you can usually get a significant discount from the book rate. JAL's "Chowari" fares, which are offered several times a year, can be incredible deals if you're willing to book months in advance. Details are usually printed in the timetable: the airfare pricing structure in Japan is much simpler than it is in America.
TRAIN
The Shinkansen, of course, is one of Japan's most famous artifacts, and it's often the quickest way to get from point A to point B. Riding in the Shinkansen is essentially like riding in a very long airplane where you don't have to keep your seat belt fastened. There's no need to check in in advance: you can just buy your ticket and go.
However, the Shinkansen network is limited: you might find yourself having to use another kind of train to get to your destination. JR operates a variety of express services on regular lines, as do some private lines like Kintetsu and Tobu Railway. Most intercity hops will use JR, as there are no national-scale private railways in Japan.
If you're taking JR, there are a variety of special tickets that can make your trip cheaper. The Japan Rail Pass, which you can only buy overseas, lets you use all the trains you want to for a specific time period. The Seishun 18 Ticket, which you can only buy in Japan, gives you five one-day passes on all regular trains (not limited express or Shinkansen) for a flat ¥11,500. Inter-regional tickets can only be bought at the "Green Windows" inside larger JR stations.
See Japanese trains and Scamming the Japanese rail network for more.
BUS
Overnight and express buses are common in Japan. They cost about the same as regular trains, but are usually much more comfortable, with reclining seats and plenty of cushioning. In major cities, bus terminals are almost always next to the largest train stations (Shinjuku in Tokyo, Umeda in Osaka).
HITCHHIKING
This isn't recommended unless you speak decent Japanese, but hitchhiking is much safer in Japan than it is in other countries, and it offers a unique chance to meet totally random Japanese (and occasionally foreign) people, as well as see the Japanese countryside that often disappears on the Shinkansen.
thanks to gn0sis for helping, as always