Whether you have decided on a cheerful sage's wandering spirit or a great warrior who has left the world only to return at a time of great peril, putting legends into your campaign can grant it an even stronger semblance of life. Every culture has their own observed customs and maintained myths: Legends are thrown into the mix as well. How can you create legends of your own for your campaign and how the party should be affected by them? Weigh in the scope first, then consider their nature, likely storytellers and if the party will encounter them or not.
Does your legend impact a particular mountain range, like a black-winged red dragon atop the cliffs outside the city? Or is your legend on more of a global level like a second moon in the sky, only visible during certain times of the year? Determine the scope of your legend so you can refine it's context from there. Local legends and global legends alike are both engaging and amusing.
Will your legend be a mighty and feral predator ravaging the countryside or a placid magical pond no one has encountered in centuries? The nature of your legend is very important for the party, and the rest of the world, to know. Harmful or helpful, adventurers will need to weigh the risks of occupying a certain area or playing a game of (potentially) mythological chicken. Work within your defined scope and decide what this creature, event or otherwise actually is or does.
Where will your party hear about this legend? Is it common knowledge? Based on how wide a region will be impacted, and the impression the legend gives listeners, map out who the most likely entertainers of it's lore will be. A giant fire-breathing horse protecting the woods would surely be known to local hunters and probably their families (if anyone has escaped with their lives). Militant threats won't be unknown to the local guard even if many of them disbelieve the lore.
Shall the party run across signs of the legend? If it's not a red herring then maybe they find former lairs or other signs of it's veracity. Legends friendly to them may one day help them, in a time of great need or just after some great deed perhaps. Unfriendly legends may end up between the party and their goal or they might just loom in the distance, while the group hopes they don't get spotted. It's an excellent climax for plot when the party can overcome those creatures formerly considered “too powerful,” as it gives their characters even more renown. Happy mythicizing!