Only sorta. Generally states or colleges require that you choose from certain majors (I couldn't have picked business, for instance).
There are certain majors that might be slightly more desirable, like math and Spanish, but looking at the major is one of many factors that decides who is going to get the job.
I think the biggest thing that has helped me get the job offers I have had is networking and practice. What I mean is...
I was offered a job with a school last year (which I turned down). The biggest thing that helped me was doing a mock interview *with someone who works for the district.* Every district has a different idea of what they are looking for. Then I had the teacher critique me, and I went over the Qs again. If she told me they used one term instead of another (i.e. "reading skills groups" instead of "reading groups"), I would write that down and bring that list of phrases into the interview with me on a small index card. It worked REALLY well. They really liked me. (But then of course I ended up turning them down =)
It also helps if you try to get field placements/practicums/student teaching in the district you want to work in. If you are unsure, try to do several different districts (it's kinda nice to see how different people do things anyway).