After browsing the forums for a while, this is the solution that worked for me.
- Install IBus (if not installed already)
- Add support for the Japanese language: System / Administration / Language Support
- Start IBus, a dialog appeared that asked to set certain environment variables. But in my case, setting these variable didn't help starting up IBus automatically when rebooting.
- To fix this, add IBus to the startup applications as described in this post.