How to reduce wind noise from a video?
The best bet is to avoid getting it on the recording.  The use of a wind cover can help break up the wind and prevent it from interfering with a recording.  Once it is there, particularly if it is really loud, there isn't a whole lot you can do about it that will result in satisfactory audio.  You can reduce it some, but it is unlikely to be able to be removed entirely and may well produce artifacts in your audio in the process.

The old adage crap in, crap out still greatly applies to audio.  Once something is mixed in to a signal, it's part of the signal.  The real world doesn't often fit digital models very well and thus there isn't a sure way to separate one part of the signal from another part.  This is why audio recordings are done with multiple tracks rather than recording everything to one output.

As far as what you can try doing with the existing audio, any software with noise reduction or wind reduction can try to reduce it or you can try to EQ the frequencies of the majority of the noise down some to help suppress it, but short of re-recording the audio and dubbing (or just re-shooting) there isn't anything I know of that will get rid of it entirely.