if it's just a simple black (or plain colour) frame, there are any number of ways to do it. the simplest i find is just to increase the canvas size slightly bigger all around, Select the area for the frame (i usually just Select the image, then invert the Selection to the frame area), then Fill with black or whatever colour you want.
if it's some fancy frame you're looking for, you probably need one of those clipart collections. there are some free webart things around on the internet, but you might have to do some tweaking or cutting/pasting to get the size you want.
There's two colour swatches on your toolbar right? click on the one in front to select whatever colour you want, that will be your foreground colour. When you "fill", choose "fill with foreground colour". That should do it.