A particulate magnetic nanostructured solid sorbent (MNSS) material is described herein. The particles of the MNSS comprise a plurality of tethered nanoparticles. The nanoparticles are tethered together by substantially linear hydrocarbon chains, a poly(alkylene oxide) chains, or a combination thereof connecting the nanoparticles in a three-dimensional elastic network with the nanoparticles as junctions of the network having junction functionality of about 2.1 to about 6. The surfaces of at least some of the nanoparticles comprise a polymerized siloxane bearing at least one sorption-aiding substituent selected from a hydrophilic group and a lipophilic group. The plurality of nanoparticles is made up of superparamagnetic nanoparticles or a combination of superparamagnetic and non-magnetic nanoparticles. The individual superparamagnetic nanoparticles comprise a passivating metal oxide coating around a core comprising at least one nanocrystalline metal or alloy having ferromagnetic or ferrimagnetic properties.