Numerous times in my life, I have been commissioned by one member of my family or another to produce some authentic-looking yellowed paper, and it can be suprisingly tricky to produce something convincing. Here's a few steps on the way to perfection:
Step One: Yellowing the paper
Take a sheet of white paper in any size. You can do this with normal paper, or thicker paper for a more convincing feel, if that's important for your purpose. Coated "shiny" paper is somewhat less effective because it doesn't absorb the colour. Ouroboros suggests the use of paper without a watermark, or the endpages cut from a book of the appropriate age.
Take a few used teabags and a cup of water. Submerge one of the teabags in the the water, and wet another just enough to produce a little of that brown tea-stain fluid. Wipe the first bag over a piece of test paper until it no longer produces puddles of water but is still leaving a healthy trail of brown stain.
Now stroke this bag across the desired paper, in a horizontal motion, until it stops producing the stain. You can now wet the teabag again, or use a new one if the old one isn't producing solid streaks or is splitting. Use the other teabag that was only slightly wet to clean up any parts that you over-saturate or to touch up any mistakes. Repeat the wetting process until the whole page is covered in horizontal streaks, which will still be easily visible as discontinuous streaks at this stage.
You now have a choice. For quickest results, dry the page with a hairdryer until it is crisp and dry; this will probably result in some curling of the page, although this is not always undesirable. Alternatively, leave it to dry by itself, which takes longer but you are unlikely to curl the paper. You could also dry it on top of an Aga, if you have one, which is something of a compromise. If it's not dried properly, the paper begins to go transparent in places and the end results looks messy.
Now streak the paper again, at various angles to the original streaks. You should eventually be left with an equal, browny-yellow tone all over the page. When you have applied sufficient layers to get the colour you desire, leave it to dry one more time.
Step Two: Making the edges
There's plenty of opportunity for personalising your paper here. You can leave the edges completely straight, which is especially useful if you plan to print straight onto the paper. Otherwise, you can cut the edges into all manner of jagged shapes or smooth curves, to simulate good ol' parchment. Bear in mind when doing this, the limitations of the next step.
Step Three: Shading the edges
If you have straight edges or only gently curved ones, you can run the edge of the paper along the hot plate of an Aga to make it turn black. However, if you don't have access to an Aga or you have very variagated edges, the best solution is to take a lighter and light the edge of the paper, allow it to burn for a few seconds, then blow it out. Move along the edge of the paper, lighting each section and blowing it out. This can be extremely time consuming, but it looks totally convincing when finished.
There you have it! This obviously takes practice, but once you get it you can have pretty convincing parchment without buying the real (and very expensive) item.
Update: Ouroboros also suggests using a mixture of coffee and orange juice as a replacement for tea. GangstaFeelsGood also suggests lightly brushing milk onto the paper and then carefully baking them in the oven, watching to ensure you get the brown colour you desire.