It depends on the type of watermark you're creating. I'm assuming you're talking about an opaque or semitransparent logo or text that is usually placed in a corner of the image.
There is a balancing act here. If the watermark is small enough, users can always just crop it out. But if you make it too large, you make the image unusable. Sometimes this is the intent (for example, look at iStockPhoto.com: they use big watermarks over the center of the image so that you can't use the image without buying it). Other times, you don't want to do this (say you're posting a wallpaper to DeviantArt: you still want people to use the image, but no one's going to use it if the watermark takes up a third of the screen).
If the watermark covers a part of the image that is not too detailed, users who know what they're doing can use the clone brush or other tools to photoshop it out of the image. (The same way I once removed ugly power lines from an otherwise beautiful sunset photo.)
Also, if the watermark is in the same place on all images, and it is transparent enough, sophisticated users can build a filter based on the common pixels from several of your images. In the right circumstances, such a filter can work like magic. (But usually it won't.)