Step 1: Install Python

On a Windows machine, first you need to install Python. The PyMol executables available have been compiled with either Python 2.6 or 2.7. I was successful in installing it along with Python 2.7.5, so my recommendation is to use that version of Python. So go here:
https://www.python.org/downloads/windows/
and scroll down until you find this line: Python 2.7.5 - 2013-05-12
and click on the Windows x86 MSI installer version. Do not download the 64 bit version, even if your computer is 64 bit.
Install Python as any other program, when you are finished you can install Pymol.

Step 2: Install PyMol

Thanks to Christoph Gohlke, PyMol executables are available along other Python based software. Follow this link:
http://www.lfd.uci.edu/~gohlke/pythonlibs/#pymol
Make sure you choose this version: pymol‑1.7.2.1.win32‑py2.7.exe
Just install pymol as any other program. The pymol executable will end up here:
C:\Python27\PyMOL\PyMOL.exe
UPDATE 3/10/2015: PyMol is now "deprecated" on C. Gohlke website, and appears to require also the installation of PMW. I saved the older executable for Windows here: pymol-1.7.2.1.win32-py2.7

Full Installation Video