The Colorado Learning Attitudes about Science Survey (CLASS) is a new instrument designed to measure student beliefs about physics and about learning physics. This instrument extends previous work by probing additional aspects of student beliefs and by using wording suitable for students in a wide variety of physics courses. The CLASS has been validated using interviews, reliability studies, and extensive statistical analyses of responses from over 5000 students. In addition, a new methodology for determining useful and statistically robust categories of student beliefs has been developed. This paper serves as the foundation for an extensive study of how student beliefs impact and are impacted by their educational experiences. For example, this survey measures: that most teaching practices cause substantial drops in student scores; that a student's likelihood of becoming a physics major correlates with their 'Personal Interest' score; and that, for a majority of student populations, women's scores in some categories, including 'Personal Interest' and 'Real World Connections', are significantly different than men's scores.