What is the earliest source that mentions Gematria?
I would say the MISHNAH in Pirkie avos Ch. 3, Mishnah 23
SimchasTorah is correct; the earliest source to use the word "gematria" is the Mishnah, Avos 3 (some editions print it as Mishnah 23 others print it as 18, but all agree it's the concluding be Mishnah of the chapter): "Says R' El(i)ezer (ben) Chisma, '[calculations of] Niddah cycles and bird offerings are the main areas of Halacha; astronomy and Gematria are parparos of wisdom." Parparos is some gastronomic metaphor, either appetizers, spices, or dessert. Gematria is either geometry or our classic letter to number expounding.
The earliest source that clearly refers to this form of numerology appears several times in the Gemara, such as the fact that yayin, wine, and sod, secret, both have a Gematria of 70, leading to the teaching that when wine goes in, secrets go out.
EDIT: I have found an even earlier source that uses Gematria in the latter sense - the last Mishnah in all of Shas, Uktzin 3:12, which says that the tzaddikim will inherit 310 worlds in the future, the gematria of "yeish" in "to bequeath to those who love Me 'yeish' (Mishlei 8:21)."
While there are Chazals that use gimatriya in an aggadic sense (as was brought regrardic יין = סוד), there is a source for gimatriya being used in a halachic sense, as well. This is in Nazir 5a, where the Gemara derives the halacha that a default Nezirus is 30 days from the word "יהיה", which has a numeric value of 30.
But the plot thickens: The Rambam in his peirush on the Mishna says that this is not an absolute d'rasha but an asmachta. Many of the mefarshei haMishna cite this view. However, see Tosafos Nazir 6b s.v Shomea. The Torah Temima (B'midbar 6,5) understands Tosafos as essentially agreeing to the Rambam, and that the d'rasha is no more than an asmachta. (Although I'm not sure why he's certain in Tosafos's words that it's merely an asmachta.)