They are not necessarily related concepts, and I think. While nudge (in Thaler's sense) is a mechanism for fostering choice in a planned way, priming refers to a faster processing of new stimuli related to recently activated ones.
It seems like the nudge of might happen through several possible mental processes, including (possibly) priming - although I personally couldn't find any example of how priming could be used to nudge a decision, I'm certain it might. None of the cited examples work through priming, though. For instance, it seems to me that the fly in the urinal example might work through a salience effect (a salient bug in the urinal makes one direct their attention to the salient object).
An example of priming (unrelated to nudge) could be when you see the word "bee", and then see a related stimuli, like the word "honey", and you recognize it faster because there's a previously activated schema. Priming might happen through a lot of means, like words rhyming or starting with the same syllable, semantically related objects, recognition of one object in an abstract pattern, etc. However, in priming there's always at least one prime (a previous stimulus) and one target (a later stimulus) and the prime will make the activation/recognition of the target faster.
Hypothetically, one could use priming to nudge people into "better" decisions if one could offer a prime related to the "best" decision (our target). For instance, consider there is a (widely known) healthy meal and an unhealthy alternative as the options in a restaurant menu. You might put a text saying "Be Healthy" at the cover, which people will see before seeing the alternatives. This might enhance the activation of the healthy alternative, and it might influence the choice (or not). While it's uncertain on whether the healthy food will be chosen, theoretically its activation will be faster due to priming.
Matlin, M. W. Cognition. Hoboken: Wiley, 2012, 8th edition.
Sternberg, R. J. Sternberg, K. Cognitive Psychology. Boston: 2017, 7th edition.