Our heroes in Middle Earth-earth knew the Nine Riders were coming even though the riders were keeping their movements secret.
”I have an urgent errand,” he said. “My news is evil.” Then he looked about him, as if the hedges might have ears. “Nazgûl,” he whispered. “The Nine are abroad again. They have crossed the River secretly and are moving westward. They have taken the guise of riders in black.” ~ Fellowship of the Ring
How did they know?
I prefer answers from canon sources, but will consider answers from the movies.