Image Processing - What Is a Gradient Domain?
You may want to read this lecture's slides on blending--They also describe Laplace pyramids as another blending tool:

Image Blending and Compositing (15-463: Computational Photography, Alexei Efros, CMU, Fall 2011)

The "gradient domain" is the name often given to a class of processing techniques which operate not on the value of the pixels in images but on differences between the values of neighboring pixels, ie. local spatial transitions.

It means that in the core computations of the algorithm, the image is represented by its first spatial derivatives (horizontal and vertical)--remember the first terms of the Taylor serie of a 1D function $f(x)$ around a point $x_0$, $f(x_0) + (x-x_0) * f'(x_0)$.

For example in the following image, for each pixel inside the white mask the image is not represented by an intensity value, but by a vector of a given direction and norm:



In the context of the stitching paper you mention, the stitched result in the overlapping region consists of a blend of the two original images which tries to respect (that is, be very close to) the observed spatial derivatives in the two images (and not the observed pixel values).