It has to be the right size, has to be 256 colors, has to have the right palleteing, and it has to have the transparency set up right.
Paste your graphics over the given example's tileset, and leave a tile filled with the transparent color in the upper-left-most corner. (EDIT: There are other ways of doing it, but this is the easiest.)
I use The Gimp, set the grid to 16x16, turn the grid on, and set it to snap to grid. It makes moving tiles easy because its automatically aligned. But you *can* do it in Paintbrush.
Gigas comes with a decent example - "Tile_Graphics_0.bmp" in the editing kit under "DEMO (source)" That's the "example's tileset" I was talking about.