Almost every linux distro I've used has support for Japanese (along with Korean, Chinese, French, Russian etc etc etc)
I favour SCIM and Anthy, but Cana and kinput2 have been around for years and years (at least since 1995 when I first tried Slackware).
What distro do you currently use? If you aren't using linux yet then try one of the live CD/DVD distros first to see what you like.
Stu