Step 5 is not a step, it is just a description of the process of embedding.
So the process is to add each byte of watermark to a random block in the original image. So in order to detect the watermark later, you need to know the seed that was used and use the same random number generator.
It doesn't say whether it detects collisions, so there is potential for a block to have a part of the water mark applied twice, so you'd need to run in reverse. In order words, generate a list of random numbers to get to the last block that would have been processed (equal to the length of the watermark) do the test or de-embedding, then step back through each random number to the beginning, to the first block processed.
It also doesn't say exactly what process to perform on the block but presumably it is reversable.