Milagrito, a detector sensitive to very high energy gamma rays, monitored the northern sky from 1997 February through 1998 May. With a large field of view and a high duty cycle, this instrument was well suited to perform a search for TeV gamma-ray bursts (GRBs). We report on a search made for TeV counterparts to GRBs observed by BATSE. BATSE detected 54 GRBs within the field of view of Milagrito during this period. An excess of events coincident in time and space with one of these bursts, GRB 970417a, was observed by Milagrito. The excess has a chance probability of 2.8x10-5 of being a fluctuation of the background. The probability for observing an excess at least this large from any of the 54 bursts is 1.5x10-3. No significant correlations were detected from the other bursts.