He traveled across India (in early 5th century), collecting and copying manuscripts, taking down all the data he heard from the mouth of tutors; went back with everything to China, and wrote a book. What material did they write on during that age? Paper was used in India long after this (probably around 11th century).
Paper was invented by Cai Lun during the eastern Han dynasty and it became a popular writing material. In Chinese, there is an idiom called "洛阳纸贵" (the papers of Luoyang is expensive), used to describe the popularity of an article. It is regarding an event in the western Jin dynasty when Zuo Si wrote SanDuFu三都赋, it was so popular that everybody was copying it, thus driving the paper price up. From this, we can gain a glimpse that paper was a common writing medium back then in China. Faxian is from the eastern Jin dynasty which was after that, so it would be natural that he used paper for his work.
Regarding the Indian counterparts, the Indians at the time often used dried palm leaves for their manuscripts. These are made from dried and smoke treated palm leaves. It was a very common writing medium in the Indian subcontinent and SE Asia back then.