There are times when you want to fake aged paper, and there are times when you feel even fussier - you want the real thing. Here I present several ways to actually age paper and to obtain old paper.
The easiest way to age paper is to use paper with a high acid content, and allow it to sit in direct sunlight, outside. Virtually all paper that is not labeled as "acid free" has some sort of significant acid content. Newsprint has the highest acid content - it will be obviously aged after a day in direct sunlight. This will work with other papers with acid content, but will take longer.
Look around in the attic. In many older houses, there is a surprising amount of older paper up there.
Another good source of old paper is old books. Do not tear pages out of complete old books that are not falling apart, especially those that are not yours, or I will hunt you down and stuff. grr. One can often find falling apart books from the 1890s for a dollar or two at many small used bookstores. These pages will often have spots to show the aging, and will usually be somewhat yellowed. Such books can sometimes be found in the dumpsters behind decent sized libraries, too.
Old paper is often available on eBay. Generally, it is a bit pricey, but it is a choice, and there is generally quite a good selection.
Though it is not paper, vellum is also an interesting old surface to write on. Old legal documents on vellum are easy to find. The writing can be removed from them by soaking the document in water and then scraping the writing off carefully with a single edged razor blade. Then wet the document again and stretch it, using staples, preferable from a staple gun, on a wood surface.
Regarding the softlink someone added to Vinland map, I am of the opinion that if the Vinland Map is a fake, that it was prodbably done on vellum of that period that had never been written on before, not vellum that was reused in the manner described above - I have seen manuscript Bibles on vellum, c. 1400, with blank leaves, sell in the $3000-5000 range - certainly within the means of someone who might forge a map like that.