If I want to go to graduate school to study physics and am a math major, how bad is it to have recommendation letters from math professors, mostly? The problem is that I just have four physics courses and after being picky about professors, I might not end up with all physics professors. Further, math professors know me better.
So, will it hurt if my recommenders are more mathematicians than physicists?
To point out one pitfall in kmdouglass's answer, there is one situation in which getting letters from out-of-discipline people can affect an applicant's chances: if the letter writers do not directly support the candidate's application to the specific discipline. In other words, if you're a mathematician applying to physics programs, your math professors should be explaining why you will be a great physics graduate student, not a great math graduate student. (Or why you will be a great graduate student in any department.) "Dissonance" between the letters of recommendation and where you're applying could make some reviewers question if you're seriously interested in applying to physics departments, which could hurt your chances (albeit perhaps only slightly).
The answer to your question is no, it won't hurt.
How you prepare your application, however, will likely depend on the type of research you want to do while working on your PhD. For your case, if you want to pursue theoretical research, then I think recommendation letters from mathematicians will be a good asset.
If, on the other hand, you want to work in experimental physics, then I still don't think it would hurt, but I would work extra hard at highlighting relevant skills and experiences, such as experience working in a machine shop or with electronics, in other parts of your application.
You still want your references to be good judges of academic performance, however. By academic, I mean that they should work in academia or be experts in research, critical thinking, and other important academic traits in your field. A life-long high school teacher, for example, may not be a good choice.
To summarize, having letters of recommendation from academics outside of your major field should not hurt your chances of getting into graduate school. The letters should speak to your character, work ethic, and natural abilities, not to the skills you possess. Those can be highlighted in your application.
Qualifications: I'm a senior (sixth-year) graduate student in a physics-related field and frequently assist my advisor in taking on new graduate students. We've taken on people with engineering, physics, materials science, and mathematics backgrounds.
I would like to speak to this issue in terms of applying to interdisciplinary programs like information science, HCI, communication etc. It matters little what the specific home department the professor belongs to as long as they can point out 2 things - 1. How are you as a potential researcher in that particular discipline that you are applying to and 2. How can they (the recommenders) recommend you in context to (1)
For instance, in my case, my recommenders came from civil engineering, statistics and computer science and I was applying to an information science department. I don't know what their recommendations contained but they could very well certify that I was doing interdisciplinary work corresponding to most areas in information science during my masters degree.
