Note: This answer is now outdated and breaks systems, e.g. Lubuntu 18.04.1 LTS on a Dell Latitude D620, such that opening Fcitx and clicking on the keyboard crashes the computer. Please pay attention to the dates and operating system for which this answer may be valid. (For example, the link in this answer leads to Lucid documentation, an OS which has now reached end of life.) If you accidentally follow this answer for a different Ubuntu version, you may need to uninstall QT4 and GTK3 packages. For example,
sudo apt purge fcitx-frontend-gtk3 fcitx-frontend-qt4 fcitx-frontend-qt5 kde-config-fcitx
sudo apt autoremove
sudo apt-get install language-pack-ja language-pack-gnome-ja language-pack-ja-base language-pack-gnome-ja-base
You might want to check out the language support metapackages as well.
A convenient way to do the latter is to run:
sudo apt-get install $(check-language-support)