I know that it's not true that $A$ and $B$ being independent given $C$ implies $A$ and $B$ are independent given $C^c$. However, I can only show this is false using a counterexample (see here for one of many).
What key ideas should I keep in mind if I want to write a proof of this that doesn't resort to using a contradiction?
Alternatively, could someone tell me when exactly the implication holds?
If you're looking for a better understanding of what's going on, the idea is that "Since $C$ and $C'$ are disjoint events, things that happen when you condition on one of them are completely unrelated to the things that happen when you condition on the other one."
To give some context, imagine that $C$ is the event "magic is not real". Then let $A$ be "you break a mirror" and $B$ be "you stub your toe". Conditioning on $C$, i.e. in a world where magic is not real, of course events $A$ and $B$ are independent, and if they both happen then it's just a coincidence. However, if you condition on $C'$, i.e. in a world where magic is real, it's possible for $A$ and $B$ to be closely connected. And all of this happens regardless of the individual probabilities involved.
To ask "When does the calculation hold?", then it can happen under many different circumstances. In particular, if $A$, $B$ and $C$ are unconditionally independent of each other, then it doesn't matter if $C$ is true or not, $A$ and $B$ will still be independent.