First, how to write an address. In Japan, the common way to write an address is like this:
Name of Perfecture Name of Region Name of Block
Name of Receiver + Kanji: -Sama
So here, we see that in Japan, an address usually started with the post code, then going from the wider area to the more specific ones. In my country, it's backwards. We started with the name of the receiver and end with the postcode. On Japanese style envelope, you have to write it top down. From a bit at the right side from the center of the envelope start writing the post code from top to bottom, then work your way to the left by specifying the address and then the name of the receiver.
A fact that you should know is that Japan's streets barely have names. So, sending a letter with a namestreet is not a viable way to do. Instead, you have to use blocks. For instance: 5-choume 5-ban 5-go (or usually written 5-5-5 for a shorthand). It means the 5th part of a region, the 5th block and the house numbered 5.
The next thing you should know is the addition of the kanji 'sama' after the name of the receiver. It is crucial to do this when sending to a Japanese, because this indicates honorifics for the receiver.
Next, to write the sender name and address, you have to write it on the back of the envelope. For Japanese style envelope, start on the right top side. Add your name and address on that side. Starting from the right most column for the Postcode and working yourself to the left. Beware when writing the name of the sender no honorifics is used. Just write your name plain. Writing no honorifics on your name made the impression that you lowers yourself to the receiver thus it is the polite way. (actually this rule also can be apply when conversing. You have to add some honorifics to the other party like: -san, -sama, -kun, -sensei, -chan, etc. But you should never try to add honorifics to yourself. It will sound pretty weird.)
i got this from p|unkouter’s blog april 2006.
Hopefully it's correct.