Interfibrillar phases and bonding in cellulose nanofibril (CNF)-based composites are crucial for materials performances. In this study, we investigated the influence of CNF surface characteristics, the guluronic acid/mannuronic acid ratio, and the molecular weight of alginates on the structure, mechanical, and barrier properties of CNF/alginate composite films. Three types of CNFs with varying surface charges and nanofibril dimensions were prepared from wood pulp fibers. The interfacial bonding through calcium ion cross-linking between alginate and carboxylated CNFs (TCNFs) led to significantly enhanced stiffness and strength due to the formation of an interpenetrating double network, compared to composites from alginates and CNFs with native negative or cationic surface charges. Various alginates extracted from Alaria esculenta (AE) and Laminaria hyperborea (LH) were also examined. The TCNF/AE composite, prepared from alginate with a high mannuronic acid proportion and high molecular weight, exhibited a Young’s modulus of 20.3 GPa and a tensile strength of 331 MPa under dry conditions and a Young’s modulus of 430 MPa and a tensile strength of 9.3 MPa at the wet state. Additionally, the TCNF/AE composite demonstrated protective properties as a barrier coating for fruit, significantly reducing browning of banana peels and weight loss of bananas stored under ambient conditions.