Vader interacted with stormtroopers in the canon novel Tarkin:
When the stormtrooper operating the equipment accidentally allowed
[Vader's meditation] sphere to bang against the edge of the cargo hold’s
retracted hatch, Vader stamped forward with his gloved hands clenched.
“I warned you to be careful!” he shouted up at the trooper.
Tarkin, p. 94
Tarkin takes place 5 years after the end of the Clone Wars and Vader's transformation so Vader was known to the stormtroopers within five years of Vader's transformation.
There were rumors that Vader was from the Clone Wars era (emphasis added):
It was that genuflecting obedience, the steadfast devotion to execute whatever task the Emperor assigned, that had given rise to so many rumors about Vader: that he was a counterpart to the Confederacy’s General Grievous the Emperor had been holding in reserve; that he was an augmented human or near-human who had been trained or had trained himself in the ancient dark arts of the Sith; that he was nothing more than a monster fashioned in some clandestine laboratory. Many believed that the Emperor’s willingness to grant so much authority to such a being heralded the shape of things to come, for it was beyond dispute that Vader was the Empire’s first terror weapon.
Tarkin, p. 73
Tarkin himself suspected Vader is the same person as Anakin and observed that Vader had already developed a rapport with the stormtroopers:
Very early on in their partnership—soon after both had been introduced to the secret mobile battle station—Tarkin grew convinced that Vader knew him much better than he let on, and that behind the bulging lenses of his face mask, whatever remained of Vader’s human eyes regarded him with clear recognition. More than anything else it was those initial feelings that had provided Tarkin with his first suspicion as to Vader’s identity. Later, observing the rapport the Dark Lord shared with the stormtroopers who supported him, and the technique he displayed in wielding his crimson lightsaber, Tarkin grew more and more convinced that his suspicions were right. Vader might very well be Jedi Knight Anakin Skywalker, whom Tarkin had fought beside during the Clone Wars, and for whom he had developed a grudging appreciation.
Tarkin, p. 73
The five year upper bound is almost certainly a significant overestimate, though. Vader was probably made known to the Imperial military almost immediately after his transformation, for two reasons:
- Vader still needed to hunt down Jedi after Order 66. Vader and the Emperor wouldn't want to waste any time and give Jedi survivors a chance to scatter and hide. Vader had already demonstrated some skill in the dark side before his transformation (e.g. he already knew how to use Force Choke...on his wife) and was capable of evil acts like murdering Jedi younglings. Vader wouldn't need much time after his transformation to start hunting Jedi again, especially if he had help from stormtroopers (which is when he would have built up the "rapport" mentioned earlier).
Vader was seen viewing the incomplete Death Star with the Emperor and Tarkin in Episode III on a Star Destroyer. A Star Destroyer requires a crew (and some of its crew members can be seen in the film) so that crew would know about the transformed Vader.
The exact timeframe for that scene is not clear, but it was probably close in time to Vader's transformation at the end of the Clone Wars since the Death Star was started before the Clone Wars ended.