[BlueRusalka]

I would say that working with a live teacher/tutor would be the best way to go, since inflection can be so important in Japanese. Where you place emphasis is a really significant, and it helps to have a native speaker or fluent person critiquing you. (Example: aME is candy, but Ame is rain.) Failing that, I've heard that Rosetta Stone's program is quite good, although I haven't tried it. If you're on a somewhat lower budget (language programs can get quite expensive >.<), there's a website called LiveMocha that allows you to take beginner language courses for free, and connects you to native speakers willing to critique your pronunciation.

Whatever you choose, you'll probably want to learn hiragana and katakana first. These are just alphabets you'll need to memorize. You can find them on the internet, or in any Japanese textbook. I found that knowing them actually helped me understand the spoken language, since from the alphabet you know exactly what sounds are possible within the language. I've actually found Japanese a lot easier to learn than French (which I studied for five years, and still don't know that well) for exactly that reason. :)

Best of luck! :)