Doing original research in Theoretical Computer Science requires a quite good understanding of almost all areas of Mathematics. I think double majoring in Mathematics and Computer science for someone who wants to do research in Theory is very important.(Or at least having a knowledge of Algebra, Analysis, Logic, Topology etc.)
I'm wondering how do graduate admission offices take this as an advantage?( Specifically in comparison with other good applicants which have publications or higher GPAs.)
Studying mathematics is great, and I agree that many theoretical computer science students would benefit from studying more mathematics. However, double majoring is definitely not a must, and it will help only slightly with admission. It could serve as a tie-breaker, but it is less important than getting good grades and much less important than doing research. Ultimately, a double major is worthwhile if you would enjoy it or find it useful, but the learning will have to be its own reward.