Mail Boxes appears in Majora's Mask and The Wind Waker. In Majora's Mask you find them scattered around Clock Town. Link can use the Mail Boxes to post letters, for example Anju's Letter. He can also get a Piece of Heart from one of them, when wearing the Postman's Hat.
In The Wind Waker Link also can use them to post letters, but this time he needs to pay to get it sent, otherwise the letter never will leave the mail box. The price he needs to pay is higher if you are farther away from Dragon Roost Island, but cheaper if you are closer. This is not all new in The Wind Waker; Link can also get letters from the mail boxes. When the Mail Box "dances," he knows that he have a letter waiting for him. It is always smart to look in a "dancing" mail box, because often there is a good thing in it.