Cellulose nanostructures have been widely studied as components of materials for a variety of applications including food packaging. They are usually incorporated as a reinforcement phase in nanocomposites (as cellulose nanocrystals or cellulose nanofibrils). In other cases, cellulose nanostructures have been used as matrices for films—bacterial cellulose (BC) deserving a special attention in this context, since it is produced as naturally nanostructured membranes, which may grow in a medium containing other biopolymers (producing bottom-up built bionanocomposites), be impregnated with other components, or be disintegrated into nanofibribils or even nanocrystals. This review summarizes findings and prospective applications of nanocellulose for bio-based materials to be used in food packaging (including active packaging).