To realize engineered materials and structures via origami methods and other folding construction techniques, fundamental understanding of paper folding mechanics and their dependency on paper micro/nanostructure is needed. Using selected papers commonly used in origami designs, we establish the relationship between the mechanical properties of fibrous paper and their corresponding ability to form and retain simple creases and mountain/valley folds. Using natural fiber paper (abaca), synthetic fiber paper (Tyvek), and a metalfiber laminate paper, we studied how the fold radius depends on the load applied using a controlled rolling apparatus. After folding, we examined the resultant micro- and nanoscale deformation using electron microscopy. In general we found that the fold radius follows a power law, decreasing with the applied rolling force. At a critical strain, each paper exhibits a transition between elastic and plastic behavior, after which the trend asymptotically approaches the minimum fold radius with increased applied force. Finally, we present examples of centimeter-scale two-dimensionally "mountain fold" patterns and relate the folding characteristics observed in these designs to the mechanical properties of the papers in folding.