They don't have anywhere else to record information.
The Galactica, for instance, was not a networked vessel. The only computer systems on board are used strictly for controlling and running the ship. There may be places in the operating systems to store notes and documents, but there's no terminals to display those on.
The same is true of the rest of the ships in the fleet. They're functional, without a lot of displays all over the place to interact with.
Other items may have been available, something like a tablet or smart device, but powering those devices would likely have been an issue. With the limited power sources available, keeping those devices alive may not have been feasible or possible, and that's supposing people had any with them. Salvaging such devices would likely have not been possible, because of the EMPs released by the duodecuple global nukings of the colonies.
I can't recall if a paper mill, specifically, was ever mentioned, but different manufacturing plant vessels were part of the fleet. It stands to reason that, whether or not the paper was in stock already or being made, it was being rationed, like any other supply.