Unauthorized camping outside of a campground in Japan is not illegal, but it is a gray area activity. In some areas it is prohibited by ordinance. If you don't follow the rules, you are not welcomed by the locals. Also, you may be questioned by the police or reported to them.
Japan is usually perceived as a very expensive country to visit; however, it is actually very possible to travel in Japan on a very tight budget. Perhaps the biggest way of massively cutting down your expenses is to do urban camping. Coupled with hitchhiking, you can effectively reduce your travel costs to food and admission fees alone.
However, you are generally not allowed to camp in parks or other government-controlled areas outside of campgrounds, so you'll have to look for private land to camp on. Permission is required. It can be very time-consuming to find a place where you can camp and get permission to do so.
First and foremost, keep in mind that if given freedom of choice, the Japanese would prefer to have their parks unoccupied by itinerant sleepers and sightseers who cannot afford a decent hotel room. If you get permission from the owners to camp, that makes everyone much more tolerant of you. If you don't get a permit, don't camp unless you really must; you are indeed doing an activity that stands on the margins of society, and so you should strive to be as discreet and respectful as possible when camping, so as to give the idea that you are a respectful traveler rather than a rude foreigner trying to freeload off Japan and its people.
If you choose to do urban camping, you will obviously need a tent, a sleeping bag and ideally a sleeping mat. You will need to carry all your stuff all day and every day, so a good expedition backpack is also essential (around 60L is a good size). Because you always carry everything, it is to your advantage to bring the lightest stuff you can find, and carry very few clothes and non-essential items, as it makes a much bigger difference than in regular backpacking.
Japan is one of the safest countries in the world, and Japan already has its own of people (usually students and drunks) sleeping in, on benches, etc., called nojuku. On top of this, in major urban centers (such as Tokyo) there are many homeless people who sleep in public parks. Although it is often misunderstood, the true meaning of "nojuku (野宿)" is to sleep outdoors without a tent, and if you pitch a tent, it becomes "yaei (野営)". Even in government, nojuku seems to refer to someone not using a tent. In Japan, homeless people are also called "nojuku sha (nojuku people)". Nojuku means to sleep outdoors without having a choice, such as because you missed the last train. But it's often the case that neither you nor homeless people are allowed to camp. Think of the fact that nojuku is not banned as a relief measure for those forced into homelessness, not as a relief measure for travel.
There are campsites in the cities as well, so take advantage of them. If you want a safe and free camping experience without breaking the rules, use one of the few places with free campgrounds. The main spots you will be looking for when urban camping are public parks, but camping is allowed in few parks or other public places. The ordinary park is not designed for camping. Also, even if camping is possible, parks, mountains, vacant lots and any other land is owned, so a permit to camp is required. Use of facilities for unauthorized camping may result in fines according to the facility's terms of use. Moreover, in some areas it is illegal to camp even with the owner's permission, due to the Natural Parks Act (Shizen Kouen Hou 自然公園法) and other laws. If you must camp, be aware of the bylaws and be sure to ask for permission.
Also be aware that bonfires are not allowed outside of dedicated campsites. If you start a fire, you may be punished by law. It is possible to have a bonfire at a campsite, but many places require a bonfire stand.
There is a historical notion that rivers (in the River Act, a river is defined as a Class A river and a Class B river [including river management facilities for rivers]) are free to be used (they are the land of the entire nation and therefore cannot be excluded by any particular owner). It is mistakenly believed in Japan that it is okay to camp anywhere along or near any river because of this. In fact, everyone is allowed to use the river beach, which is a natural area, and you are responsible for any accidents that occur. No unauthorized bonfires are allowed there either. Most managed areas, such as river management facilities and parks, are either prohibited for camping or require a permit from the owner. Also, camping is not allowed in protected ecological areas, even on river beaches. Since the beginning of 2000, there has been an increase in heavy rainfall and rising rivers, so take extra care when camping on river banks.
Some general tips to remember:
Below are some more area-specific tips.
You'd probably want to camp in the parks because of the high cost of lodging in Tokyo, but most of the parks in Tokyo are outlawed by the Tokyo Parks Ordinance (Tokyo to Kouen jourei), which prohibits camping. However, that doesn't mean you can't camp in Tokyo. Of course you can camp in camping grounds.
Most cities do not have the handy street corner maps like in Tokyo, so the first thing you should do when arriving in any city is get a map from the tourist office in the train station. Also, like in all cities, in the train stations there are maps of the immediate surroundings.
You can also do the convenience stores' atlases method, but it's usually not necessary, you will probably be fine with a paper map (from the tourist station) and the train stations' maps.
There are a few other ways to sleep in rural areas.
Here's a list of places where you can camp for free.
Caution. This may include places where the rules prohibit overnight stays and tent-pitching. In parks and other government-controlled areas, people are generally not allowed to camp outside of campgrounds. Please get permission from the management to camp to avoid trouble. A person writing may be introducing you to a place where you have broken the rules. Even if you are able to camp with permission on private property, etc., it is not a place to stay and should not be listed. It is an annoying and ungrateful act. Be sure to check that the terms and conditions of the location state that camping is available. You can also avoid problems if you allow other readers to review the terms of service.
Obviously, when you camp everywhere you do not have always access to showers or washing machines, as you would if sleeping in a hostel.
For washing yourself, there are a few methods.
If the weather is warm, you can wash in public parks, using available water. The disabled toilets are spacious and convenient, but they are intended for the disabled, so please do not use them.
If it's cold outside or you do not want to wash in public parks or toilets, you can go to onsen (hot springs) or sento (public baths). In practice there is no real difference between the two, so just ask for the cheapest (they are usually around ¥400).
In the big internet cafes (such as Manboo Cafe or Media Cafe Popeye) there are sometimes showers available. They are usually free (if you also use the computers) but there is sometimes a fee. By the way, do not hesitate to take advantage of almost all Internet Cafes' "unlimited free drinks" policy!
You can wash your clothes by hand or find laundromats, which can be found pretty much anywhere.
If a situation arises where you have to sleep in the park for a reason (last train, etc.), nojuku is allowed. If you want to sleep in nojuku, do not pitch a tent. Using a tent is not nojuku and may be a violation of the ordinance. The police are the only people who are likely to wake you up. They will care most about checking your identity to determine whether you are illegally living in the country. If they see you sleeping during the night, they will most likely wait until morning to tell you to leave. In Tokyo, if you sleep in the big homeless spots, you should pack up by 06:30. After this hour it is likely that the police will come to tell you to leave, but nothing worse will happen. Everywhere else, if policemen see you they may tell you to leave. Some parks also have security guards, who will also usually wait until morning to tell you to leave if you are not out soon enough in the morning. You may also be approached by the police in the same way, even if you are camping on private property or other property with permission. If so, be respectful.
Camping provides the greatest amount of freedom. Just make sure to follow the rules without fail.