Watermarks are added under Settings > Image Upload
Your watermark image is best as a png with transparency, but you can use any image type you like.
They are permenant, the image is recompressed with the watermark embeded at your chosen location so there will some loss in quality, but not really noticable to most people, but keep a backup of your images if you have watermarks enabled.