I get asked this question once every few months, and thought I'd try putting some of the answers together for everyone to look at.
The most important thing to remember is that every author is different: what works one time could be the wrong approach the next.

Once you stop to think about it it's fairly obvious, but most Japanese authors are good in Japanese, not English. Sure, you can write them in English, and sometimes you will get an answer, but they make their livings writing Japanese, and you are coming to them with a request, so be considerate.
It also shows them that you probably can really read and write Japanese, and therefore you probably can translate their babies into English.

There are a variety of rights attached to literary creations, and you would probably be interested in the right to publish and sell a translation of the original work. There is no such thing as "translation rights," although it is often mentioned. You can translate anything you like into any language you like, without telling anyone, and not be breaking any law. If you publish it, however, the situation is very different. It makes no difference whether you publish it for free or with a pricetag, the legal problem occurs when you make it available to other people without the permission of the rights holder of the original work.
And as the names suggests, the rights holder owns the rights. If you publish first and ask for permission later, you may find yourself in court, and the Berne Convention provides an international framework for infringement suits if the rights holder is so inclined.

So, you've read a fantastic work and want to translate it.

The first question to ask is, Why?
If you want to translate it for the sheer pleasure, go right ahead and you can skip most of this article.
If you want to see the translation published, however, somebody will have to ask the rights holder for permission. Normally that would be the publisher, but if the publisher does it for you then you wouldn't be reading this blog.

Before you can convince an author to let you publish his (or her, of course; ditto below) creation, you have to find him. Most authors are good at hiding, but often you can ferret them out. The most obvious place to look is on the Internet, because the author may have an official website, and if you write a reasonable email to the website it will usually be read. If you can get into contact with the author directly, you stand the best chance of reaching a quick and simple agreement.

A lot of authors don't have official websites, and especially not dead authors. Not surprisingly, there are a lot more dead authors than live ones. If the author has been dead for at least fifty years his works are probably in the public domain. The Aozora Bunko site lists these public domain authors and has many of their works available for free in text form. Warning: Just because an author died more than half a century ago does not mean that everything he wrote is now public domain! It may have been published (and copyrighted) posthumously, by someone else. It may have been revised, and a new copyright issued. Other surprises can happen.

If copyright still exists on the work you want to translate, you have to locate the person with authority to handle rights, whether that's the copyright owner or the copyright administrator. That might mean the author, the author's estate, or some literary agency somewhere, for example.
One excellent resource is the 文藝年鑑 , which is published every so often (I think every two years), and available on Amazon. It has an extensive (but still woefully incomplete) list of contact information for both living and dead authors, sometimes with an actual address and sometimes with just the name of the person to contact at the Japan Writer's Association (日本文芸家協会), which serves as agent in many cases. It has a variety of other useful information as well.

If that doesn't work, and in my experience it only works maybe half the time, try literary associations. Obviously you can't just call up and ask them for a phone number, but you can ask them if they'd be willing to forward a letter to so-and-so for you. Usually they are.
If you work in a particular genre you may be able to get membership in a particular association, which makes things even easier. Membership qualifications vary, but generally you'll need recommendations from existing members to get in, so make it a point to meet and mingle with people in that field. You may be able to ask them for a favor, and merely being able to say that you are a member of the appropriate society can be very useful when asking an author to consider you.

For example a few related Japanese associations I belong to are:

1. 日本推理作家協会 (both mystery and SF authors)
2. 日本ペンクラブ (mostly mainstream authors)
3. 歴史時代作家クラブ

If all else fails, the last option is to write to a publisher of the work you hope to translate. I have had very poor luck with this approach, for several reasons. First, many publishers are simply not interested, and your letter vanishes into black hole somewhere. Of the publishers that are interested, most of them hope to serve as literary agents and make a little more money off the author's works. Often the response includes a demand for a hefty advance, or imposes various conditions. And of course every so often you run into a publisher who is actually willing to work with you to just get the author published in English!
The above-mentioned 文藝年鑑 also has a long list of publishers, most with address and phone number but rarely a URL. You can also just search Google for the publisher's website, and get the address that way.