I am using the ZpFocus Theme and the Random Image. The "Random Gallery Image" watermark text appears on the image. Is there a way to remove this watermark? Thanks.

yes, you have to edit the sidebar.php file (go to admin - themes - edit) and remove
`

`
This is the part which displays the overlay text.

Can anybody help? I removed the div as explained however the random title overlays are still displayed.
Any advice would be great.

Not familiar with this theme. But if this is a real watermark in the image there are several places where to set watermarks. The global options, the options for each album and even for each image indivicuall (priority in that order). You may need to disable the watermarks there first (the random images functions if the theme uses these do not have a parameter to disable watermarks if I recall right. Info on that on the documentation.
You need to clear the image cache after you changed the settings to see any effect.

dendraya has the correct solution.

it is not a true "watermark" and is created by the code dendraya mentions. (or similar code, just noticed how old this thread is...)