Just set your machine to one of the pre-set fancy stitches, and send your paper on through! Do some testing first on scrap paper because, as you can see on the envelope in the picture, some stitches are too close together and tear the paper.
Of course you can also do fancier things by disengaging the feed dogs on the machine and doing a little freehand sewing, too.
Sewing-machine perforations can also give you the easy-tear functionality of perforated paper.
If you're writing a letter, this looks great in a hand-stitched envelope.