Bio-nanocomposites based on poly (vinyl alcohol) (PVA) and cellulosic nanostructures are favorable for active food packaging applications. The current study systematically investigates the mechanical properties, gas permeation, and swelling parameters of PVA composites with cellulose nanocrystals (CNC) or nano lignocellulose (NLC) fibers. Alterations in these macroscopic properties, which are critical for food packaging applications, are correlated with structural information at the molecular level. Strong interactions between the fillers and polymer host matrix were observed, while the PVA crystallinity exhibited a maximum at 1% loading. Finally, the orientation of the PVA nanocrystals in the uniaxially stretched samples was found to depend non-monotonically on the CNC loading and draw ratio. Concerning the macroscopic properties of the composites, the swelling properties were reduced for the D1 food simulant, while for water, a considerable decrease was observed only when high NLC loadings were involved. Furthermore, although the water vapor transmission rates are roughly similar for all samples, the CO, N, and O gas permeabilities are low, exhibiting further decrease in the 1% and 1-5% loading for CNC and NLC composites, respectively. The mechanical properties were considerably altered as a consequence of the good dispersion of the filler, increased crystallinity of the polymer matrix, and morphology of the filler. Thus, up to ~50%/170% enhancement of the Young's modulus and up to 20%/50% enhancement of the tensile strength are observed for the CNC/NLC composites. Interestingly, the elongation at break is also increased by ~20% for CNC composites, while it is reduced by ~40% for the NLC composites, signifying the favorable/unfavorable interactions of cellulose/lignin with the matrix.