An android app list without any IMEs listed is like a person without an arm.
(Having re-read re-thought about the OP, jettyke was posting apps for Japanese immersion on the go I think. Not simply a "Good apps for your Japanese phone" kind of thing. Regardless, I'll leave my post as is since you need IMEs to work with Japanese content.)
IMEs:
ATOK
The Japanese IME on this superb and its kanji conversion prediction is probably one of the better ones that I have seen on the android. That said, it costs 1,500yen and the trial version only goes for 15 days. Its one of the few Japanese IMEs though that has a somewhat decent English input in my opinion. The word prediction is pretty good so long as you type everything in correctly. ATOK does not have auto word correction though which makes it a pain for me to use. The QWERTY keyboard design is pretty decent and pretty close to the Gingerbread default which I like a lot, but without the auto-correction, it still makes it hard to use. It has a unique flick style input system which I found easier to use than the usual hanabi style flick. Additionally, it has support for inputting cell phone emoji codes which most IMEs don't add. I believe if it had automatic english correction I would pay for it.
MultiLing
Since I'm not using ATOK anymore what I am using is MultiLing. MultiLing is actually multiple IMEs; you have to download plugins to use other languages. The things I like about Multiling is that it uses the Gingerbread keyboard design which is much easier on my big fingers compared to others (see Simeji). It has awesome english word prediction and correction. Finally, you can switch between languages by swiping the space bar which I have found to be way more convenient and easy to use than pressing a button for some reason. The kanji conversion prediction is ok in my opinion, but I still find myself wishing it was as fluid as the Google IME on my computer.
Google IME Beta
I actually just saw this when I was looking on the market for links. A rudimentary check on it shows that kanji prediction is probably as decent as the computer IME version. It pops up place names that I usually have to enter letter by letter sometimes. That said...IT HAS NO AUTO-CORRECTION. I like the keyboard design and input is very fluid but trying to use English input on this would be a test in paitence as you would have to constantly go back and fix errors like "Englush." One thing I kind of like though that I just played around with a bit more is the layout for symbols. You simply hit the 信号 button and it has stuff laid out in tab style menu that you can slide through which is nice. It also has a menu for 顔文字 with a decent number of entries but there isn't an easy way to add new entries, nor is there an easy way to add new words in general. If you long press on the data box and get the Edit/Copy/Paste window to pop up, you can add the word just behind the cursor, to your dictionary, but I think that might be a system wide dictionary. All-in-all, very fluid, smart layout, but little in the way of features and customization. This is beta though.
Simeji
Any talk of IMEs that excludes Simeji isn't worth its stuff. Simeji was probably the first Japanese IME on Android that non-Japanese phone users could use to get Japanese input on their phone. That said, I've never liked it really. The kanji prediction is horrible and sometimes leaves you scrolling through lists to find what you need. The English prediction wasn't any better. It does have auto-correction though. It has some very superficial skinning as well. The number one reason why I avoid this IME though is the keyboard design is quite horrendous. Keys are blocks on the screen that you hit instead of circles or blocks with spaces between them. I found myself hitting other buttons way more on Simeji compared to any other IME on my phone. It is because of this that back before I found Multiling, I would always switch to a native English IME if I had to do any sort of long typing in English.
EDIT: Added a bit more on the Google entry.
Edited: 2012-01-15, 2:14 am