In my setting , there is a faction known as the Templar that serve a larger Empire. The Templar are all magically gifted and immortal (non aging). They are covered completely in their armor and their helmets obscure their faces to the enemy.
The Templar are pretty much always the vanguard. They are the tip of the spear that breaks the enemy's back and allows the "lesser" troops to finish up. The Templar aren't just muscle though. They employ varied and advanced tactics, but have a (well earned) reputation for brutal efficiency. The Empire isn't the most stable place, so the Templar are often used to put down rebellions; basically to "prove a point".
Due to this fact, they also try to nurture this reputation in the Empire as well, so that someone doesn't meet an Imperial citizen and have say something along the lines of: "Oh, the Templar? Nah, they're pretty cool dudes. My sister married one. Really nice guy." Rather, there should be mixed stories and wild rumors like: "They once burned down a city for selling bad wine" or "One got his head cut off by a knight. He killed the knight and just sewed his head back on after the fight!"
Now, onto the real question: How can the Templar effectively spread propaganda among a populace to cause fear and superstition when it comes to fighting them?