Between Episodes III and IV, when and how did Darth Vader obtain/construct his red lightsaber?
Vader built his lightsaber within five years of his fall to the dark side
Cross-referencing Wookieepedia's timeline of canon media and article on Anakin Skywalker, I believe the canon source which first depicts Vader after his fall to the dark side in Episode III is the novel Lords of the Sith. The events of that novel occurred five years after Episode III, and the novel does mention that his lightsaber is red:
The red line of Vader’s lightsaber flashed, deflecting the shots back at the Twi’lek, putting a dark hole in his chest and another in his face.
No canon source appears to describe how he built it (or if it was given to him), but presumably he built it just as he built his lightsaber as a Jedi.
In Episode III, Revenge of the Sith, Anakin had a blue lightsaber.
In Episode IV, A New Hope, he has a red lightsaber.
Therefore, he acquired it in the 19 years between those two.
As Wookieepedia says here:
Darth Vader's lightsaber was the personal lightsaber of Darth Vader, a Sith Lord. He built the weapon some time after his fall to the Dark side of the Force at the end of the Clone Wars. It replaced the one he lost during his duel with Obi-Wan Kenobi on Mustafar.
It is common for Force Users to build their own lightsabers; for example, Luke's new one in Episode VI.
In Legends, we have something more concrete. In Dark Lord: The Rise of Darth Vader, which takes place directly after episode three, Vader creates his lightsaber. he is seen here with the new lightsaber in Chapter 9:
In his quarters aboard the capital ship now under his personal command, Darth Vader, gloved and artificial right hand clamped on the hilt of his new lightsaber, knelt before a larger-than-life hologram of Emperor Palpatine.
And in Chapter 13:
Sidious had provided the synthcrystal responsible for the crimson blade, along with his own lightsaber to serve as a model. Vader, though, had no fondness for antiques, and while he could appreciate the handiwork that had gone into fashioning the inlaid, gently curved hilt of Sidious's lightsaber, he preferred a weapon with more ballast
So yes, he made the lightsaber in 19 BBY, directly after Episode III, in Legends.
In Legends, less than a month.
Bol Chatak was one of the few Jedi that managed to escape Order 66. She was killed on Murkhana in a lightsaber duel with Vader, by which point he had his red saber. This took place less than one month after the events of Episode III.
In Disney Canon, definitely within 5 years, possibly within a month
As Null says, the earliest canon reference to Vader's saber is Lords of the Sith, which takes place 5 years after Episode III ends, though it is apparently mentioned in the novel Tarkin that Vader performed an execution for the Emperor on the planet Murkhana, so the event that occurred in Legends may still be true. This cannot be proven definitively, however, because we aren't given any details. I think it would be safe to assume that Vader had a red lightsaber before going on any missions, though.
Short answer: he probably built it very early on. Perhaps as early as just prior to his final scene in RotS. (The one with Tarkin & the Death Star under construction in the background.)
Due to the way the scene is shot and edited it's not possible for it to be visible on screen if it is there, but the prop was certainly made for the movie and it's shown up in promotional photos of Hayden in the armor, so it seems reasonably likely it was part of his costume for that last scene.
As to when that scene takes place: it's tough to say exactly. That final montage seems to cover at least a few days, if not weeks. Assuming one is to take the order the scenes are presented as the literal chronological order of events (which may not actually be the case) then this scene falls right between Padme's funeral and Bail returning home to Alderaan with baby Leia.
The scene is somewhat revisited in the Rogue One tie-in novel Catalyst, albeit from Krennic's perspective and though it doesn't give any more clues than the movie, the context of what's being said certainly gives the impression this is still a matter of days--a week at the outside--after Order 66. Indeed the Emperor is said to still be recovering from his encounter with Windu.
Mind you, even if they didn't end up using it in that scene, it still seems likely Vader would have built a new one ASAP. At this point he would have built at least three others as Anakin so he certainly knows what he's doing. Resources shouldn't be a problem as Catalyst depicts the Empire is suddenly flush with spare kyber crystals in the wake of the Temple massacre. (See the Ahsoka novel for how a reclaimed Jedi kyber can be turned into a red blade.)
First ever explanation (but ambiguously canon in Legends)
The other answers explain the Legends and Disney canon explanations, but I'd also like to throw out the first ever explanation (even if it was ambiguously canon even at the time), which was in the Star Wars Episode III: Revenge of the Sith video game. This came out on May 4, 2005 which was released 11 days before the movie.
In an alternate ending, Anakin kills Obi-Wan Kenobi in their duel. Emperor Palpatine arrives on Mustafar and hands him a new red lightsaber, then Anakin kills him with it.
As we can see, the Emperor already had the red lightsaber ready to give to Vader. It stands to reason that Palpatine gave it to Vader as soon as he had recovered enough to use it.
Granted, this relies on whether Palpatine having the lightsaber is still C-canon (according to the Legends classifications system) despite the ending itself being non-canon.