The story
Attested since the early 17th century. An onomatopoeia for rapid exhalation, as one may make when a trying situation is over, or in order to get rid of an unpleasant odour. Compare Scots feuch, Spanish fu, Czech fuj, and many more such forms.
Etymology from Wiktionary, CC BY-SA 4.0.