If it's a retail card, consider checking with the manufacturer about warrenty issues associated with replacing your own fan. Get something in writing if possible. Now for the fun. Look into something like the Thermaltake CrystalOrb from Newegg, 2Cooltek, Plycon, or your favorite retailer. Then look at your card. If the HS/fan is clipped on, it's easy. Just pop the clips and off comes the heatsink. Clean off any old thermal interface material with rubbing alcohol. Apply a thin layer of your favorite thermal compound like Arctic Silver. Then carefully clip on the new heatsink and off you go.
The above is easy but chances are it is glued on with some sort of glue. Now comes the fork in the road. You can either let the heatsink heatup to soften the glue which is done with 30-60 minutes of continuous loops of your favorite stress tester like Q3. My person favorite is to put the card in the freezer for 30 minutes to make the glue brittle. Either way you slip 2 credit cards in between the PCB and heatsink. Then take a flathead screwdriver and give it a gentle twist. The old HS/fan should pop right off. Clean off the clip with rubbing alcohol to remove any old glue or thermal compound. Next is another fork in the road. You can either glue on the heatsink with four small dabs of epoxy on the corner of the NVidia gpu plus thermal compound in the middle or use a purpose made thermal epoxy like Arctic Silver Thermal Epoxy or use the provided thermal tape. Thermal tape is quick and painless and can allow yout to remove the heatsink if needed. It does not provide the best thermal properties but it works. Many members have done the glue on the four corners but I prefer using arctic Silver epoxy. It is pretty much permanant and has the same heat transfer properties as regular Arctic Silver.
As a side note, test the new HS/fan first. It would suck to glue it on and realize it is a dud. Chances are slim but why risk it? Also be careful when handling the CrystalOrb, some people have put too much pressure on the top which acts as a finger guard. The pressure bend the metal enough to prevent the fan from spinning. Not good.
Best of luck.
Windogg