How do I exchange a non polarized Christmas light plug with a polarized plug?
Because the original plug is non-polarized and can be plugged in either way, you can just use a polarized plug. It just limits you to plugging in one way. 

The more important issue is the fuse. Because the lights were provided with a fuse, we have to assume it is unsafe to omit it. It is certainly against the electrical code to omit it. 

You can buy an in-line fuse holder and splice it into the (now) hot wire, right next to the plug. Just make sure to get the same amperage fuse (rated to at least mains voltage).