Those are raster texture images placed in Illustrator. Probably scans of actual paper. Scott's answer will do in a pinch but that's not what's going on in the samples you provided. They're a little more convincing than Illustrator's effect.
SubtlePatterns.com has some very nice paper textures to choose from. You could also try your hand and building your own tileable texture.
I've done a screen shot version of how to quickly create a tiled patten before. Here's the quick run down.
- Place the texture of your choosing
- Use a transform effect to move and duplicate the linked/embedded file horizontally with as many duplicates as needed.
- Apply another transform to cover the vertical dimension
- Apply a clipping mask to restrict the texture to your desired area
- You can apply a background color to the clipping mask and blend the placed text into it