As you explained, the query posed by the title is meaningless, but 0 degrees Celsius + 0 Celsius degrees is handled correctly: http://www.google.com/search?&q=0+degrees+celsius+%2B+0+...
Should Google should convert the query somehow? It seems like adding two temperatures in degrees Celsius is something that never really makes sense (or subtracting, multiplying, or dividing them), so faithfully executing it like they currently do is rarely what's intended.
Did you mean: 0 degrees Celsius + 0 *Celsius degrees*
If I wanted to know 50 degrees Celsius + 35 Celsius degrees, I would probably omit the units and just ask for 50 + 35. I find it unlikely that many users actually run into this problem.