Here is the tex file I use:
Basically, edit the sender and receiver, save the file as envelope.tex then run
pdflatex envelope.tex
pdf2ps envelope.pdf
lpr -o landscape envelope.ps
I wrapped this all in a zenity script to make it easier for me, but this is pretty easy for a couple here and there.
Code:
\documentclass{letter}
\usepackage[left=1in,top=0.15in,papersize={4.125in,9.5in},landscape,twoside=false]{geometry}
\setlength\parskip{0pt}
\pagestyle{empty}
\begin{document}
Sender Bob
505 Main St.
Anytown, CA \ 92666
\vspace{1.0in}\large
\setlength\parindent{3.6in}
Receiver Joe
200 Second St.
Sametown, PA \ 08754
\end{document}