It's really best to let Apple do it under warranty as there may be other issues. For example, the fan itself may work, but is not being activated because there is a faulty sensor that is not turning it on. And if one fan has been trying to do the work of both, then the one that is working may be compromised by excessive running. Finally, it's possible that heat from the fan not working could have damaged the logic board.
The first thing to do is to run the Apple Hardware Test and see what it shows. It is on your Install DVD #1--instructions are on the label.
Then you should go to a local Apple authorized repair shop as The Fat One has suggested and show them the results of your AHT. They might want to run further diagnostic tests. But they should be able to determine what is wrong and what parts are needed and order the parts in advance so that you could schedule a time for the repair and drop it off and pick it up in a day or two.
It may even be that you could arrange for a loaner while yours is in the shop--you could always ask. But I've heard of this being done.
I don't know if you have 3 year Applecare, but if you do, you paid good money for it so you may as well use it.
But because your problem is likely more involved and expensive than just replacing one fan, I would really recommend arranging for Apple to do the repair.
Good luck!