The quest for advanced water purification technologies has been vigorous over recent decades, motivated by the promise of ever more efficient, greener, and affordable tools. Halloysite nanotubes (HNTs) are naturally-occurring materials that have shown potential as dye sorbents. Unfortunately, these nanoclays suffer from low permeation during water treatment, which limits their widespread application. Here, we use cellulose nanocrystals (CNCs) as structural scaffolds to support HNTs and fabricate permeable aerogel sorbent materials with mechanical stability. Aerogels containing 40 wt% HNTs showed a maximum dye adsorption capacity of 60 mg g-1 towards methylene blue, with only 15% decay in efficiency after 5 cycles. The good mechanical properties of these materials allowed for their incorporation into free-flowing purification columns that displayed excellent dye removal ability. Overall, this work provides a new strategy to fabricate green, renewable, and low-cost sorbent materials for the removal of dyes and shows potential for the sorption of other ionic pollutants.