From Zelda Wiki, the Zelda encyclopedia
Mail Boxes appear in Majora's Mask, The Wind Waker, Phantom Hourglass and Spirit Tracks. In Majora's Mask, Link finds them scattered around Clock Town. He can use the Mail Boxes to send letters, like Anju's Letter, for example. He can also get a Piece of Heart from one of them while wearing the Postman's Hat.
In The Wind Waker, Link also can use them to send letters, but this time he needs to pay to get it sent, otherwise the letter will never leave the mail box. The price he needs to pay is higher if he is farther away from Dragon Roost Island, but cheaper if he is closer. Link can also get letters from the mail boxes like in Majora's Mask. When the Mail Box "dances," he knows that he has 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.
Mailboxes in Phantom Hourglass are very similar in appearance to their The Wind Waker counterparts, even including the "dance" they do when new mail arrives. Link can only send one letter, which is the Prize Postcard, which the Man of Smiles gives him. The winged Postman will always deliver letters in person, but only when Link approaches a mailbox. Technically speaking however, the Postman only reads them to Link, never actually giving him his own mail.