Does anyone know the restrictions one might face if they are a graduate student in a computer science program (let's say doing theory) and they become interested in taking a course from the mathematics department or become interested in working on mathematics problems? Is this something where you need to full on change departments or is it generally more acceptable?
This is frequently very easy: the boundary between mathematics and computer science is pretty blurry, especially for the more theoretical side of computer science. In many universities, you will even find classes that are shared between math and computer science departments.
I suppose that If you are a masters' student, you might run into problems fitting in the classes that you want to take if there are a lot of other program requirements. For Ph.D. students, however, there are typically less constraints.
It depends somewhat on your advisor, and less on departmental policies. If you can convince your advisor that you need to take some math courses to be more comfortable in your research, its unlikely you would be prevented from doing so by the dept.
Of course, if your advisor wants you to focus on research and not take any additional courses, that may be an issue - but you can still take the class informally (non-credit).