We assemble 121 spectroscopically confirmed halo carbon stars, drawn from the literature, exhibiting measurable variability in the Catalina Surveys. We present their periods and amplitudes, which are used to estimate distances from period-luminosity relationships. The location of the carbon stars - and their velocities when available - allow us to trace the streams of the Sagittarius (Sgr) dwarf spheroidal galaxy. These are compared to a canonical numerical simulation of the accretion of Sgr. We find that the data match this model well for heliocentric distances of 15-50kpc, except for a virtual lack of carbon stars in the trailing arm just north of the Galactic plane, and there is only tentative evidence of the leading arm south of the plane. The majority of the sample can be attributed to the Sgr accretion. We also find groups of carbon stars which are not part of Sgr; most of which are associated with known halo substructures. A few have no obvious attribution and may indicate new substructure. We find evidence that there may be a structure behind the Sgr leading stream apocentre, at ~100kpc, and a more distant extension to the Pisces Overdensity also at ~100kpc. We study a further 75 carbon stars for which no good period data could be obtained, and for which NIR magnitudes and colours are used to estimate distances. These data add support for the features found at distances beyond 100kpc.