How free are you to take mathematics courses as a computer science graduate student? 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.