Will a UK Android telephone work in Japan?
Sim-locked phones need to be unlocked for use on other carriers.  Almost every phone you get will be sim-locked.  The most easily unlocked phones I know of are the Galaxy S line.

The only other thing you need to check is the radio frequency bands used by the device and the carrier.  If they match, you're in luck.  "Quad-band" devices should work on every GSM network.