cheap relays, check if the fan is pulling to many amps which can cause excessive arcing when the fan relay is engaged, also check the signal wires to the relay for shorts which can cause the electro magnet to blow.
Consider installing a 30A (or whatever is appropriate) circuit breaker in front of the relay. I'm talking about the kind that replaces a spade-style fuse. You can get a spade fuse in line plug. Circuit breakers are meant to absorb amp spikes. They have a larger built-in range, and they reset themselves if that upper range is exceeded.
With all due respect, I don't know how to answer that question. If you have never tried to do these things before I'd advise against just diving in. Perhaps you could find someone who you trust, and who knows a bit about this subject, to give you a hand. On the one hand you want to learn how to do these kinds of things; on the other, the idea is to get it fixed without messing something up further (although this latter result has happened to all of us).