Molecular spiders are nanoscale walkers made with catalytic DNA legs attached to a rigid body. They move over a surface of DNA substrates, cleaving them and leaving behind product DNA strands, which they are able to revisit. The legs cleave and detach from substrates more slowly than they detach from products. This difference in residence time and the presence of multiple legs make a spider move differently from an ordinary random walker. The number of legs, and their lengths, can be varied, and this defines how a spider moves on the surface, i.e., its gait. In this work we define an abstract model of molecular spiders. Using Kinetic Monte Carlo simulation, we study how efficiently spiders with various gaits are able to find specific targets on a two-dimensional lattice. Multi-legged spiders with certain gaits can find the targets faster than regular random walkers. The search performance of spiders depends on both their gait and the kinetic rate r describing the relative substrate/product “stickiness”. Spiders with gaits that allow more freedom for leg movements find their targets faster than spiders with more restrictive gaits. For every gait, there is an optimal value of r that minimizes the time to find all target sites.