DEFINITELY use a relay from your remote and run the power and ground to your + and -.
The problem with running it off your remote wire is that it will draw all its current through the remote turn-on lead. These typically don't have much current capability, being made to turn on a few devices... they are usually in the neighborhood of 250-500mA in my experience. Your fan may draw more than that, causing you not only to blow the fuse in your remote lead, but can actually short out the remote from your headunit.
If you run it off a relay, the remote can trigger it, and the power will turn on, just like if it were an amplifier or something. In this way, you could run 10 or more of them without worrying about current draw.