Japan has one of the lowest scores on international English tests and has taken steps in recent years to improve English language teaching at schools with increased instruction and greater use of native English speaking teachers alongside Japanese teachers in the classroom.
Having said this, jobs are more scarce now than they used to be and in recent years it is becoming harder to find work in the popular cities like Tokyo or Osaka. Jobs can still be found, but you may well have to try harder for them and offer more. Part of the reason is the overall downturn in the economy but also recent problems such as the earthquake in the north.
By law you need a degree to obtain a visa to teach in Japan. A TEFL Certificate such as the ICAL TEFL Certificate will also increase your chances of getting work as there is more competition for work than there was a few years ago. In addition, having a TEFL/TESOL qualification will also entitle you to increased salary at some schools (especially the larger chains).
Some countries have an agreement with Japan which entitles their citizens aged 30 or younger, to a working holiday visa regardless of whether they have a degree or not. Check with your embassy to see if your country is one of those who have undersigned this agreement with Japan.
Having said this, in some cases it is possible to bypass the requirement for a degree. For this, you will need considerable teaching experience and visa sponsorship from your employer.
Speaking Japanese is by no means necessary although it can help you secure a job in some cases. And also being pleasant and well dressed will also make a difference.
Ideally it is best to find work before you go, however often teachers will find work once they are in the country. What often happens in practice is that teachers go to Japan on a 90 day tourist visa then have interviews at different schools (telling immigration you are there as a tourist, of course). Once you have a job the school will help you change your visa to a working one.
Although you can sometimes get the visa in Japan, often it will mean a quick trip out of the country to Singapore or Hong Kong (also good for shopping!) and then coming back on the new visa. Sometimes the school will help pay for this. It can take from a couple of weeks to a few months to change the visa.
As well as many smaller schools, there are several major chains of language schools in Japan. There are a high number of Eikawas or "conversation schools" where the emphasis is on conversation classes. However, you will also need a good understanding of grammar as traditional language learning is still very common.
You may also be able to find work - especially if you are not fully qualified or have less experience - in a company in-house course. Some large companies offer their employees English lessons as perks; sometimes they will take on English native speakers without qualifications for these positions.
The working week is usually around 30 - 35 hours. Pay is around 250,000 JPY or $3150 USD (€2492, £2004) per month which is enough to live on reasonably well but from this you'll likely have to pay a lot in accommodation which will begin at about 60,000 JPY or $750 USD (€593, £477) per month.
Eating out can be expensive so it pays to manage your money well till you are familiar with costs and expenses.
Private or hourly lessons can pay between $10 USD (€8, £6) to $35 USD (€28, £22) per hour.
Old hands advise newcomers to bring at least $5000 USD (€3956, £3182) with them as it may be a month before the first paycheck comes in and there are a number of setting up expenses to deal with right at the start of the contract, notably the cost of renting an apartment which, with the deposit, can be about 3 or 4 months' rent.
Note that unlike many other countries, permanent foreign residents in Japan are not entitled to welfare benefits when they get old and are in need. This should be borne in mind if you are considering remaining in Japan for many years and then retiring there.