Icons are added as icon_resources 

setup( 
    windows = [
        {
            "script": "with_gui.py",
            "icon_resources": [(1, "myicon.ico")]
        }
    ],
)

The same practice works as well for console and windows scripts. The resource number does not seem to matter. Windows just takes the first existing icon.

/!\ if somebody knows how to add small and large icons, speak up...

Hm, doesn't the .ico file contain them?

does the resource number refers to the icon's index in the .ico file (if containing > 1 icons) ? -- [mailto:dswsh@plasa.com dody wijaya]

How to add small and large icons

You must create ico file with two icons in one. Your icon file must contain small ico (size: 16*16 pixels) and large ico (size: 32*32 pixels). For WindowsXP you probably may create a big ico (48*48) - but it's only for XP. Almost all popular icon editors can create complex icon with small and large part in one.