It used to be required on an annual basis. Fortunately they've improved the fans since the early 90's.
You need to find a (quiet) fan with the same airflow or higher as what you have now, and the same mounting holes. The fans are almost all standard 12 Vdc so you clip the 2 wires going to the existing fan and solder, crimp or use wire nuts to connect the new fan in its place. Make sure you get the airflow direction correct and the voltage polarity correct (+12 to +12 , gnd to gnd).
It's pretty easy. Just make sure you get the right screws when taking the cover off the power supply. If you loosen a heatsink screw by mistake the supply could fry when you putit back together.