Install binary packages
Multimedia packages are made available on many alternative repositories, often because of distributions restrictions on available codecs due to patents in some countries (mainly US for the moment).
Everything would be perfect in a wonderful world if package builders would contribute to official distributions, and multimedia editors chose only free codecs to promote their use worldwide ... So try to stick to distributions deliveries?
Debian, Ubuntu and derivatives
Debian project ships Kdenlive packages since "squeeze" (6.0) release, however to benefit from recent updates and bugfixes you might consider upgrading to a "testing" release or even "sid".
Ubuntu also offers Kdenlive since "gutsy" (7.10), but for similar reasons it could be preferable to upgrade to the latest release.
In both cases a simple
apt-get install kdenlive should then work.
Fedora, RedHat and derivatives
RPM packages are not yet maintained in official branch, so you must go through unofficial RPM Fusion repository. Follow the site recommendations to make them available and end with
yum install kdenlive
Gentoo, Arch, BSD ports
Building scripts are ready for up-to-date systems, so run respectively
emerge kdenlive or
pacman -S kdenlive or
pkg_add kdenlive, etc.
Kdenlive and MLT can compile and run under Mac OS X. Packages are available from the MacPorts project.
MacPorts is a source-based system - there is not a binary app bundle for Kdenlive. Therefore, Kdenlive and all of its numerous dependencies including multimedia libraries, KDE, and Qt must be compiled. This can take a long time and much disk space! Furthermore, it is not unusual for something not to build correctly; it is definitely not something for the novice, impatient, or "faint of heart."
For more details see this
Installing from source
If you want to test latest committed code or your personal patches, you will have to build Kdenlive (and probably MLT) on your own.
You can use your distribution's package building procedure to use its software management system to install/upgrade/remove the binaries and data, and eventually share your builds (and even contribute to package maintainance - refer to the respective distribution manual).
If you prefer you can build & install Kdenlive to a local area (preferably not /usr, but rather /usr/local or $HOME/my_local_builds/kdenlive-last-release or similar). It is then recommanded to use the build script 
- on distributions older than Debian 6 or Ubuntu 10.04 and derivatives, you need to set
ENABLE_SWFDEC=0in the config variables of the script