We have obtained moderate resolution (~6 km s-1) spectroscopy of several hundred M giant candidates selected from Two Micron All Sky Survey photometry. Radial velocities are presented for stars mainly in the southern Galactic hemisphere, and the primary targets have Galactic positions consistent with association to the tidal tail system of the Sagittarius (Sgr) dwarf galaxy. M giant stars selected from the apparent trailing debris arm of Sgr have velocities showing a clear trend with orbital longitude, as expected from models of the orbit and destruction of Sgr. A minimum 8 kpc width of the trailing stream about the Sgr orbital midplane is implied by verified radial velocity members. The coldness of this stream (σv ~ 10 km s-1) provides upper limits on the combined contributions of stream heating by a lumpy Galactic halo and the intrinsic dispersion of released stars, which is a function of the Sgr core mass. We find that the Sgr trailing arm is consistent with a Galactic halo that contains one dominant, LMC-like lump; however, some lumpier halos are not ruled out. An upper limit to the total mass-to-light ratio of the Sgr core is 21 in solar units. Evidence for other velocity structures is found among the more distant (>13 kpc) M giants. A second structure that roughly mimics expectations for wrapped, leading Sgr arm debris crosses the trailing arm in the southern hemisphere; however, this may also be an unrelated tidal feature. Among the bright, nearby (<13 >kpc) M giants toward the south Galactic pole are a number with large velocities that identify them as halo stars; these too may trace halo substructure, perhaps part of the Sgr leading arm near the Sun. The positions and velocities of southern hemisphere M giants are compared with those of southern hemisphere globular clusters potentially stripped from the Sgr system. Support for association of the globular clusters Pal 2 and Pal 12 with Sgr debris is found, based on positional and radial velocity matches. Our discussion includes description of a masked-filtered cross-correlation methodology that achieves better than 1/20 of a resolution element velocities in moderate-resolution spectra. The improved velocity resolution achieved allows tighter constraints to be placed on the coldness of the Sgr stream than previously established.