For a file to be executable in linux, it has to be given permission to do so. This is done by the command: chmod a+x filename
... which doesn't make the executable automatically Do The Right Thing.
Actually, it might be a bad idea to +x .exe files, since you don't execute(*) them, and they most certainly aren't valid code in any format (a.out, ELF) used by GNU/Linux.
(*) `execute' is here used in the strict sense: running the file however sh does it (probably by looking for a #! line, then looking in magic, and then just assuming it's a shell script).
Of course, you could add an entry to magic telling that .exe-files are windows executables (if it isn't there already--nautilus automagically knows).