To answer my own question after having figured it out. If anyone needs it, this is what I did to get it working:
Install anthy, uim, and prime:
apt-get install anthy uim uim-xim prime
I had previously installed also anthy and uim compiled for XQt for the Zaurus and it was conflicting with the debian versions, so make sure to uninstall anthy and uim-xim if you had it installed on the Zaurus.
Then to get Japanese input running when in debian, add the following line to your ~/.xinitrc config file:
export XMODIFIERS=@im=uim
Then to start Japanese input running the Prime predictive input software:
uim-xim --engine=prime &
Then to switch to Japanese input you hit shift-space and you can enter text.
Prime is a predictive text input, similar to QPOBox, and you can use it also to enter text predictively in English. It gives you options based on what you entered before and facilitaties typing...
For this there is the following problem: anthy when activated with shift-space sends then the Japanese wide space, known as zenkaku supeesu, instead of the regular Western half-character size space, hankaku supeesu.
To fix this, edit the /usr/share/uim/japanese.scm file once in debian. Find the lines that read:
(define ja-direct-rule
'((" " " ")
))
In the middle line the first space between the quotation marks is the regular English one, the second one is the Japanese wide space. Change this line to:
'((" " " ")
So that both spaces between the quotation marks are the hankaku spaces.
Now when you enter the text using Prime, it will send the regular English space between the words, when you hit space, and not the zenkaku Japanese space.
Don't know of any other way to let you then select the zenkaku space if you need it though.