This is not easy, but it is possible using at least two different approaches.
First, gcc can be configured as a cross-compiler and as such, it can generate Windows applications from Linux. Don't ask me how to set up cross-compiling though, I wish I knew (I'd use it the other way around if I did).
Second, there is a gcc drop-in replacement which runs the compiler on a different machine via ssh. I forgot its name, but it is hosted on Sourceforge, should be easy enough to find under "compilers".
That way, you need another PC (or a virtual machine running on the same PC) with Windows installed, and you can compile Windows applications natively, doing the actual work from Linux, though. It is a bit less elegant than cross-compiling, but it surely needs less setup.