You get mailboxes by crafting a red box like the ones you can see in the Rusty Nymph tavern. You then drop the box on your vendor. Your vendor will prompt you to tell him how to advertise the box. You type in "______'s Mailbox" and then go lock it down outside your house. It is best to lock the box, as then most players cannot look inside of it, but they can still drop things off in it. A GM may help you to get a mailbox if you are having trouble. - Submitted by Warren N.