I know you can get them from Mother Screng, but not how...

You get magic tatoos in Homlett at the workers camp there.

OK, someone claimed it was in Nulb... So how do I get them. There's only one guy in the camp (Dex), and he doesn't do anything.

You might have to go there at night. In the daytime most of the camp is empty because the peeps are all at the castle construction site. Or maybe it is the other way around.

IIRC, a female NPC does it, and you just need to talk to her and get the right dialogue options for her to offer to make a tattoo. Her tent is sorta towards the middle/eastern part of the camp

The mystical tattoo permanently takes up a space in the backpack of the NPC who gets it, and it increases their Intimidation skill IIRC.

You can get two different tattoos, one in Hommlet and Nulb. Yes, you might need to visit the Hommlet camp at the right time. Both are acquired by simply following the right conversation tree. In Nulb, I think the first question is asking what she does there. Just keep trying every possible branch. It shouldn't be terribly hidden.