1. From here download the file named gs904w32.exe (for 32-bit Windows) or gs904w64.exe (for 64-bit Windows).
2. When you double-click on the downloaded .exe file, installation will start automatically, no need for Command Prompt and stuff.
3. Run Scribus. It will probably recognize the location of GS automatically, but in case it didn't, go to File > Preferences > External Tools and under "PostScript Interpreter" specify full path to the .exe file (if you haven't changed the path during installation process, it will be something like: C:\Program Files\gs\gs9.04\bin\gswin32c.exe).
Thanks also for this explanation (and for all the great people involved with Scribus). I'll say to any future lurkers, what caused me confusion and frustration was that in the Scribus Preferences, it appeared to correctly show the "gswin32c" destination. However, it apparently wasn't reading it at all. So, I then followed Step #3 above and specifically selected the "gswin32c.exe" from that "bin" folder, and then, at last, Scribus recognized Ghostscript.
So some people might get thrown off by the fact that Scribus appears to be already looking in the proper destination, and yet you still have to go and designate this path for it, anyway.