Install new KDE desktop theme

Just extract the package to ~/.kde/share/apps/desktoptheme/

Eg:

Download Caledonia theme.

Then,

tar -xvvf ~/Downloads/Caledonia.tar.gz -C .kde/share/apps/desktoptheme/

Now, visit the Desktop theme menu to set this as default.

Login screen theme:

Apparently there is no interface to change these, for regular users. However, the location is:

/usr/share/kde4/apps/lightdm-kde-greeter/themes/