OK, it’s probably more accurate to say “flame resistant” or “flame retardant” paper, because the flame does actually damage the paper, but it just blackens and won’t catch fire or burn on its own. The treatment couldn’t be simpler: soak the paper in a saturated solution of borax (sodium tetraborate decahydrate) in water, then let it dry. Alum (potassium aluminum sulfate hydrate) is also commonly used for this purpose, but not quite as easy to find. Borax is available at most grocery stores.
Thanks to Ron Tozier for sharing this video.