Applications of nanocellulose as a water treatment material are being actively pursued based on its interesting properties, such as renewability, large specific surface area, hydrophilic surface chemistry, and biodegradability. This study used carboxymethyl cellulose nanofibrils (CMCNFs) to prepare a typical bead-type adsorbent with improved structural stability as an actual water treatment restoration material. In addition, a cationized nanocellulose adsorbent was prepared by introducing polyethyleneimine (PEI) on the surface of the CMCNF (P/CMCNF), the removal efficiency of Cr(VI) was evaluated, and its mechanism was elucidated. As a result, the P/CMCNF beads showed an excellent Cr(VI) removal capacity of 1302.3 mg/g, the best result among cellulose-based adsorption materials. Cr(VI) was effectively removed by electrostatic attractions combined with chemical reduction and chelation mechanisms. Furthermore, the macrobead fabrication and PEI surface modification process improved the underwater stability of the P/CMCNF, and it showed excellent reuse efficiency.