Law 38 covers run out. However, in this case it's Law 28 - Wicket down that is the relevant one.
In the case above, Law 28 section 1, clause V covers it - if both bails are dislodged, the fielder can effect a runout by either replacing a bail (as you suggest, although only 1 bail is required) OR by removing a stump from the ground with the ball in the same hand as the stump.
The old fable of taking out a stump and touching the ball to it while held over the head is simply that, a fable.
In your question, I think the umpire erred in giving the runout, unless bails had been dispensed with - see section 4 of law 28.