Having fallen to their most chastening loss of the season at Vicarage Road two months ago, Ole Gunnar Solskjaer's men exacted revenge in style as they followed up Monday's Premier League victory at Chelsea.
Fernandes' nonchalant penalty gave the hosts a half-time lead that Martial and Greenwood superbly added to in a 3-0 victory that moves United up to fifth, just three points behind the Blues.
United paid tribute to the late, great Harry Gregg, hero of the Munich air disaster, before kick-off at Old Trafford, where January signing Fernandes calmed the nerves in a superb individual display.
The Portuguese tucked away the penalty he won, thanks in no small part to a skip in his run-up, with Martial showing similar coolness when clipping the ball past former United goalkeeper Ben Foster in the second half.
Troy Deeney had seen an equaliser ruled out minutes earlier after the video assistant referee adjudged Craig Dawson to have handled in the build-up – a moment that took the wind out of Watford's sails.
Greenwood, still only 18, hit a powerful strike off the underside of the bar to complete United's victory, although substitute Odion Ighalo went agonisingly close to marking his Old Trafford debut with a goal against his former club.
Victory ended in a straightforward fashion, but it had not started so comfortably.
Perhaps feeling the impact of Thursday's Europa League exertions at Club Brugge, United were struggling to complete simple passes and make easy decisions.
Luke Shaw's timely intervention thwarted Deeney and saved his team-mates' blushes early on, with Abdoulaye Doucoure turning the ball into the side-netting as Solskjaer's side appear intent on shooting themselves in the foot.
Aaron Wan-Bissaka wasted a glorious opportunity to net his first goal in red after Foster failed to deal with a Daniel James cross, while David De Gea came to the rescue at the other end when more poor play led to a Doucoure shot.
The first half looked set to end goalless, but flying Fernandes had other ideas as he drew a foul out of Foster. Referee Martin Atkinson awarded a penalty and United's big-name January signing stepped up to casually slot home.
Half-time allowed Watford the chance to settle and Shaw had to be alert under pressure to turn behind for what looked to be a costly corner as Deeney turned home after Dawson saw his effort come back off the post.
The away fans' celebrations were wild but short-lived as VAR adjudged Dawson to have handled. That moment changed the course of the match, with United stepping up a gear.
After Greenwood's cross-shot went across the face of goal, fellow forward Martial found the net. His initial attempt may have been saved by Foster but he collected the ball, turned and clipped a cheeky effort into the net.
United were determined to build on that 58th minute goal, with Greenwood, James and Harry Maguire all having attempts to add to the feel-good factor.
Greenwood would eventually find the net with 15 minutes remaining.
Racing from inside his own half, the 18-year-old played the ball wide to Fernandes and collected the return pass before firing home off the underside of the bar in front of the Stretford End.
It was the final goal of the afternoon – but not the last time the woodwork would be rattled.
Gerard Deulofeu saw an attempt clip the bar and Ighalo had a strike deflected onto the post by Adam Masina after rounding Foster.
Fellow substitute Tahith Chong also went close, while Scott McTominay came on for his first appearance in two months for the hosts.