At my school we don't have valedictorians, but we do have dean's medalists (one for each major "college" like Business, Science, Social Science, etc), and one president's medalists (selected from the dean's medalists).
It definitely doesn't depend on GPA or how many majors the person had. Each department (Chem, Bio, Physics, etc. for the College of Science and Mathematics), nominates a person based on not only their grades, but how active they were with various things (including community service... and of course, for the sciences, research credentials are a big plus). Eventually, the dean picks among the departmental nominations, and the president picks among the various dean's medalists. Definitely not just GPA based... at least at my school.