How do STEM researchers know if their research is actually novel?

The honest answer is: you don't know, and thus the phenomenon of multiple discovery. Sometimes this is simultaneous, and other times it is independent, as for example in the case of conductive polymers, which were apparently rediscovered and lost several times.

Now, in practice, you must do a reasonable literature search, and part of the training that one receives over time is how to figure out how large a reasonable literature search is. It also helps to participate in conferences, where one becomes generally familiar with the thinking and knowledge in one's field. Submitting one's own work for peer review and presenting it in talks also offers opportunities to be informed of connections that one was not aware of.

While this may seem embarrassing, in fact, as long as one is doing one's reasonable due diligence, it is not worth being embarrassed about. This is because it's very rare for rediscovery to happen in the same context. There's a staggering amount of literature out there, but the number of problems is even bigger, and so any given specific piece of work may actually have startlingly few people in a position to conduct it.

Thus, rediscovery in practice often heralds a new connection being made between fields. In this case, the recognition of rediscovery often opens up the "unaware" side of the interaction to be able to import and adapt results that were based on the prior work, thus rapidly advancing the new area in which those results are being applied.

In short: do your due diligence, but don't fear discovering you've reinvented the wheel.

Scientific advances happen within niches, so the existing literature isn't as overwhelming as you might think. We read a lot, but we also read selectively. During our PhDs, we need to get up to speed on all that has been done so far in our general area of interest, and after that, we just need to stay up to date. I read fairly widely in oceanography and fairly widely in environmental modelling, but certainly don't read everything published in these fields. I read a larger proportion of what is published in the general area of coastal biogeochemistry, and a larger proportion again of what is published in coastal biogeochemical modelling, but still by no means everything.

But I do aim to read (or at least skim) everything that is published regarding the coastal biogeochemistry of my favourite geographical area, and everything that is published globally regarding the physiology of the particular biogeochemically-important micro-organism that I am particularly interested in at the moment. That only requires me to read half a dozen to a dozen new papers each year that relate very specifically to my own research area, in addition to the (much wider) general reading I do to stay on top of related recent developments.