There are at least a couple of ways to add a border to an image in GIMP. I'll describe two ways below — one method is easier but it modifies the image size slightly; the second method keeps the original image size, but has more steps.
The sample image for this tutorial is a screenshot from uncyclopedia.org. The starting dimensions of the image are 490x260 pixels.
Here is the original image without a border:
The filter to add a border is in Filter > Decor > Add Border:
You will then have options to set the width of the border. In this case I'm adding a 2px black border around the image:
This method adds to the dimensions of the image. Adding a 2px border around the original 490x260px screenshot expands the image dimensions to 494x264px:
Once you have used a filter, you can repeat it on other images by pressing Ctrl-f. That makes this the fastest way to add a lot of borders with GIMP. The only drawback with this method is that it changes the image dimensions.
This 2nd method has more steps, but it keeps the original image dimensions.
First press Ctrl-a to select the entire image. Then go to the menu item Select > Shrink and shrink the selection by 1 or 2 pixels depending on how thick you want the border.
Then press Ctrl-i to invert the selection. Press Ctrl-l (lowercase L) to bring the layers window into focus. Create a new layer with the default settings:
The border will be added to this new layer.
Press Shift-b to choose the paint bucket tool. Choose the color you want to use for your border. Then zoom into the image and click inside the selected border area on your image. In th following image I'm zoomed in 800% so that I can fill the 2px wide selected area around the image:
Here is the final result. It is the screenshot with a 2px black border around it, but the border is painted over the image so that the image still has it's original dimensions, 490x260px: