How free are graduate students to choose research topics given their department?
This will vary based on your adviser, your level of study (i.e. what degree you're going for), your committee and your department.  In almost all cases for computer science, you will be required to demonstrate mastery of the subject.  Incorporating outside knowledge from another subject area, say, cell biology, where you re-implemented or improved a gene matching algorithm, for example, would probably be allowed.

Simply doing an experiment from cell-biology with no tie-in to CS would almost certainly not be approved--but, this is where your adviser, et. al. come in.  If you've got a smashing idea, a good adviser/committee will help you try and find a way to tie it into your degree and PhD students are typically given more leeway here than Masters students.

Though, be prepared, in some cases, an adviser will play a big role in determining what your thesis will be.  Also, if you are being funded by a particular grant under a PI (principal investigator--typically a research professor), it is traditional (at least at my University) to pursue research related to what the PI is doing.  Though it's definitely easy just to ask to be exempt from this tradition.

So, basically, the answer to your question is it depends.  Almost certainly you will be required to do something Computer Science-y for a CS degree, but there can be a lot of leeway in determining what Computer Science-y means.