This is the first of a series of papers devoted to the investigation of a large sample of brightest cluster galaxies (BCGs), their kinematic and stellar population properties, and the relationships between those and the properties of the cluster. We have obtained high signal-to-noise ratio, long-slit spectra of these galaxies with Gemini and WHT with the primary purpose of investigating their stellar population properties. This paper describes the selection methods and criteria used to compile a new sample of galaxies, concentrating on BCGs previously classified as containing a halo (cD galaxies), together with the observations and data reduction. Here, we present the full sample of galaxies, and the measurement and interpretation of the radial velocity and velocity dispersion profiles of 41 BCGs. We find clear rotation curves for a number of these giant galaxies. In particular, we find rapid rotation (> 100 km/s) for two BCGs, NGC6034 and NGC7768, indicating that it is unlikely that they formed through dissipationless mergers. Velocity substructure in the form of kinematically decoupled cores is detected in 12 galaxies, and we find five galaxies with velocity dispersion increasing with radius. The amount of rotation, the velocity substructure and the position of BCGs on the anisotropy-luminosity diagram are very similar to those of "ordinary" giant ellipticals in high density environments. ; Comment: Accepted for publication in MNRAS