Shortcut ;-)
Skins for KM 1.5.x can mainly be found here:
http://kmeleon.sourceforge.net/wiki/K-MeleonThemes15 kmeleon.sourceforge.net/wiki/K-MeleonThemes15
And of course in this forum here, but you found that already
To apply them open your KM folder in Explorer (not the browser, but the file manager).
It contains a folder "skins", in it are all skins, each has their own folder.
Copy the new one there too, then start KM and click Edit/Preferences/GUI to choose one of the skins. Needs browser restart.
If you don't know how to find the skins folder, you could alternatively open KM and click Edit/Configuration/Macros, then go up one level.