What do positive and negative gradient values mean for Convolutional Neural Network?
As you know, the purpose of gradient maps like these is to show which pixels are contributing most to the prediction.


  The specific question . . . is why the positive values of gradient maps mean that object was detected there? 


It's not positive/negative values that matter, but rather the magnitude of the gradient.  If the gradients associated with a pixel are small in magnitude, then that pixel is likely to be unimportant to the prediction (since small changes in the pixel's value translate to small changes in network outputs).  By contrast, if the magnitudes of the gradients are large, then it signifies that the pixel is important to the prediction.


  Why here the highlighted gradients maps have parts of dog/bird/spider highlighted?


It looks like the authors of the paper are post-processing the gradient map with a function they call $\psi$.  Notice the following passages from section 4.2 (highlighting was added by me)


and



The authors are taking the absolute value of the gradient.

So the gradient maps from this paper only show the magnitude of the gradient, not the sign.  When you see a part of the image highlighted, it doesn't mean that the gradients were positive.  Rather it means that the magnitude of the gradients were large.  Blueish regions correspond to near-zero gradients (low importance), while the orange-red regions correspond to large gradients (high importance).

Hope that helps!