GIF will allow you single-color transparency, while PNG has full alpha channel support.
See also GIMP Watermark removal
Resynthesizer allows you to remove watermarks and similar from an image. Download it from the GIMP Plugin Registry or my wiki. Move all files to GIMPPortable\Data\.gimp\plug-ins\.