Windows Live Messenger skin resources are contained in a file called msgsres.dll located under Program Files\Windows Live Messenger directory. Most skins are available as an msgsres.dll file that needs to be placed in the Windows Live Messenger directory in Program Files.

1) Make sure Windows Live Messenger is not running in the system tray
2) Go to the Windows Live Messenger directory and rename the existing msgsres.dll file to msgsres.dll.old
3) Paste the new msgsres.dll skin file in the directory
4) Start WLM and enjoy the new skin

Below are some excellent recommended skins for Windows Live Messenger 8.1:

EvO
WLM Bluesky
Mac Messenger Final
Minimal Messenger
Unknown Messenger
Windows Vista Basic
Windows Office Messenger
Windows Vista Messenger Black

Visit Messenger Stuff for more skins.

The EvO skin is one of my favorites.