Those envelopes by Tomoko Fusè are really easy to fold, and really cute. You can simply write inside the envelope, or slide your folded letter inside the envelope. The instructions can be found in “Home decorating with origami”, ISBN 4889960597, pages 38, 41 and 46. There are many other cute models.
Papers: envelopes from A4 printer paper, decorations (stoppers) from 7,5 cm (japanese chiyogami for the crane, washi for the flower) and 9 cm (boat on the right). She recommends 7,5 cm but I find 9 cm looks better – probably a culture difference, I like gaudy better than discreet elegance :) The finished envelopes are 10,5X10,5 cm.