This is the first in a series of articles devoted to deformation quantization of gerbes. Here we give basic definitions and interpret deformations of a given gerbe as Maurer-Cartan elements of a differential graded Lie algebra (DGLA). We classify all deformations of a given gerbe on a symplectic manifold, as well as provide a deformation-theoretic interpretation of the first Rozansky-Witten class.