Milagrito, a detector sensitive to gamma-rays at TeV energies, monitored the northern sky during the period February 1997 through May 1998. With a large field of view and high duty cycle, this instrument was used to perform a search for TeV counterparts to gamma-ray bursts. Within the Milagrito field of view 54 gamma-ray bursts at keV energies were observed by the Burst And Transient Satellite Experiment (BATSE) aboard the Compton Gamma-Ray Observatory. This paper describes the results of a preliminary analysis to search for TeV emission correlated with BATSE detected bursts. Milagrito detected an excess of events coincident both spatially and temporally with GRB 970417a, with chance probability $2.8 \times 10^{-5}$ within the BATSE error radius. No other significant correlations were detected. Since 54 bursts were examined the chance probability of observing an excess with this significance in any of these bursts is $1.5 \times 10^{-3}$. The statistical aspects and physical implications of this result are discussed.