You do this using the pywin32 (Python for Windows Extensions) module.
To make it run at startup you could mess around with services but it’s actually much easier to install a link to the exe in the users “Startup Folder”.
Windows 7 and Vista
c:\Users\[username]\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup
Windows XP
c:\Documents and Settings\[username]\Start Menu\Programs\Startup