Does casting blindness on a Medusa (or other gaze using creature) stop their gaze attack?
Yes, a blind Medusa cannot use its petrifying gaze.
The petrifying gaze of the Medusa says:
When a creature that can see the medusa's eyes starts its turn within 30 feet of the Medusa, the medusa can force it to make a DC 14 Constitution saving throw if the medusa isn't incapacitated and can see the creature.
Same for basilisks. While their petrifying gaze is a bit different, they also have to see the target creature.