What's the relation between WSS and Web Parts?

Nothing but pure relation. WSS is the engine for all SharePoint services, remember? Without WSS, there won't be any SPS sites and without an SPS Site, you won't have an Web Part Zone and without Zones, you can't place Web Parts. Further, WSS is central to all SharePoint services without which, there won't be any way to store user specific Web Part customization parameters, no mechanism for proper administration procedures such as backups, restores and configurations. No mechanism to support web farms and scalability and no mechanism to manage users, their roles and assignments to particular SPS site groups. WSS is the heart of the SharePoint Service engine and a Web Part is just a tiny subset of the whole picture but yet makes a powerful difference to the whole user experience.