Whether it's an electric fan or your own lungs, it's pulling energy from storage (a battery or your own chemical energy storage) and converting it to kinetic energy. It's no different than if you put the fan or your face in the water facing backwards to propel the ship.
That seems too dismissive of the part that’s counter-intuitive, and I think this is legitimately counter-intuitive, which is why physics professors are losing bets.
The fan on the boat is blowing air forward from behind the sail, and by it’s very presence on the boat, it applies a force to the boat that is trying to move the boat in reverse. Without the sail, the boat does move in reverse. It’s surprising that one can seemingly recover more force to push the boat forward than was already used to push the boat in reverse. IIRC Myth Busters confirmed the result but didn’t come to a detailed conclusion as to why, which could involve the shape of the hull, directions of the hull & sail relative to the fan direction, or some aerodynamics of the air blocked by the sail.
In any case, I think it’s quite different from putting the fan in the water facing backwards to propel forward.
