Personally I think that temples, palaces, forests and villages are the classic environments for this kind of characters. A good source of inspiration could be this beautiful game (one of my favorites): The Legend of the Mystical Ninja. This game is filled of references to Japan culture in the classic Sengoku era.
Viewing post in 16x16 Samurai Fantasy Characters comments
@Kokusai, check out the Edo/Three Kingdoms tilesets by BB-Bits! They have so many tilesets with east asian style, theme and buildings. There's also the popular Ninja Adventure pack by pixelboy that fits the japanese theme for your next game!