I taught there for 7 years or so. The language isn’t really a problem within the bigger cities - you’ll soon pick up enough to get by, and all the trains are signed in English - but it can be an issue out in the sticks. OTOH, if you want to get fluent fast, working in some village where no-one speaks your language is best. Tough, but best.
Finding a job is relatively easy in the big cities - there’s a fairly high turnover, and the bigger companies {Nova, ECC, Berlitz} are always recruiting: they run regular ads in the English language newpapers, or in the local gaijin magazines. They’ll also sponsor you for a work visa, which you’ll need if you don’t want to work under the table: a work visa is invaluable, since a lot of people sign on with the big companies, work for a couple of months or a year or so, then move on to smaller schools or high school teaching.
However, you will need the minimum of a bachelor’s degree to get visa sponsorship - it’s a government regulation to keep out the riff-raff. The only alternative is to sponsor yourself, which is possible but a huge pain in the arse: you’ll need to prove you have an income of at least 250,000 yen per month, which means getting enough jobs to cover that - often hard, if you’re unqualified or inexperienced - getting income declarations from your employers, and then doing the paperwork yourself. The advantage of getting sponsorship is that they’ll do the paperwork for you.
If you’re from NZ, Australia or Canada {and some other places I forget - Ireland?}, there’s a 6 month {extendable to a year} working holiday visa, which doesn’t require a degree, but I guess that’s not an option for you.
The bigger companies will also set you up with accommodation, which is a big bonus. I worked for Nova, who recruited me here in NZ - they recruit in Japan, but also have overseas offices: the American one is in Boston, although there were plans to open one on the West Coast. It’s a huge advantage being recruited where you are, since they’ll arrange everything before you even step on the plane: you even get met at the airport!
You can just turn up there off your own bat, find accommodation and present yourself at one of the company offices, of course - Lonely Planet and similar guides give all the addresses you’ll need, and there are a few guides to finding a job in Japan out there - but if you can find someone to do it for you, why not?
Enjoyable? Definitely. I stayed a little longer than I planned, but the life is a lot easier than you’re led to expect - the stereotype of crowded trains and miniscule apartments only holds true in the centre of the big cities - I lived in a shoebox in the middle of Osaka for 18 months or so until I’d exhausted the bar scene, then moved to a larger and cheaper apartment in a nice suburb - and it was still only 30 minutes from Osaka by train. You’ll meet some cool people {and a few dickheads}, have some fun, and drink a lot: I even got a wife and son out of the deal!
I hope that’s helpful: lemme check my archives and do some Googling, and I’ll see if I can come up with some contact addresses and numbers for you.