We give a complete characterization of polynomials in two com-plex variables that are cyclic with respect to the coordinate shifts acting onDirichlet-type spaces in the bidisk, which include the Hardy space and theDirichlet space of the bidisk. The cyclicity of a polynomial depends on boththe size and nature of the zero set of the polynomial on the distinguishedboundary. The techniques in the proof come from real analytic function the-ory, determinantal representations for polynomials, and harmonic analysis oncurves.