Hi there Koala and welcome to the Guild! First off, which version of GIMP are you using? If you are using version 2.8 the you will need to use the "Export" rather than "Save as" feature since the "save as" will only save .xcf files. If you are using version 2.6 or below though then it is fine to use the "save as" feature (there is no export feature for 2.6 and older versions.
Second, if you are correct in that you do need to export/save the .gif file in the brushes folder which, if you are using windows, ought to be located under: Users > GIMP 2.6 or 2.8 > Brushes. When you hit the save as or export feature it should pull up a pop up window and you should be able to find your Users folder on the "Places" section.
Hope that helps.