Both are correct grammatically. You could remove the "to them" part since it's really not required in the sentence, but it's still correct nonetheless. Normally at least, the "to them" or the "from the office" etc is added to the sentence after the "relayed XYZ's instruction" bit.
The sentences ideally would become :
- The butler relayed to them Eugene’s instruction to use as little
seasoning as possible.
- The butler relayed to them Eugene’s instruction that they should use as little seasoning as possible.
As pointed out by Bill Franke, the first is an order, and the second is a recommendation.
Other that that, depending on the context, both sentences are correct.