SELinux, fully known as Security Enhanced Linux, was a pet project of the NSA that has garnered international contributors. It's a mandatory access control system using the Linux Security Modules framework, and will protect any exploits discovered via apps, daemons, or other vulnerabilities. Using SELinux will control general access to files, devices on the system, and sockets, giving individual users minimal access to needed items only.
Security-Enhanced Linux comes standard on Red Hat Enterprise Linux version 4 and higher. For free release distros that don't come with SELinux as a standard, there is support for six distributions and work currently in progress for support on two others. Currently supported free distros are: Debian, Hardy Heron 8.04, Fedora 2+, Hardened Gentoo, Yellow Dog, and EnGarde Secure. Work in progress support includes SUSE and Slackware, though for the time being, it appears work has stopped.
Pros and Cons
The purpose of SELinux is essentially to protect the machine in every way possible, where that means keeping hackers out, and preventing users from entering malicious code or sloppy apps from opening a gaping hole. It can used in "enforcing", "targeted", and "strict" modes, and made as lenient or strict as you'd like.
If you're a user not interested in running the security system during all working hours, it can also be used to analyze new apps after installation for security concerns. For example, when working on a controlled system that has been carefully combed for vulnerabilities and made as secure as possible, you'd want to see exactly what security vulnerabilities any given app might pose. Using reporting, you can monitor which applications require security enhancements. An app can also be tested on a non-sensitive machine and monitored for SELinux alerts, exposing issues that need repaired before the program can be used on a sensitive machine.
SELinux is by no means for everyone, and will likely prove frustrating for low-end users. Unless your threat level is elevated, you perform or host sensitive duties/data, or you're in a position another would readily take the opportunity to exploit, SELinux isn't necessary. There can be issues with running your apps without permissions after installing/activating SEL, leading to frustration and the possible disabling of the security system in favor of a simpler--but less secure--environment. A good firewall and anti-virus system will keep most Linux systems secure, though you may very well be surprised at the number of probes you see over your system ports while running SELinux (even if they are just looking for Windows vulnerabilities), and that alone may be worth the learning curve for you.
Installation is dependent on the distribution you're installing it on. If you're looking to implement a fresh Linux system with SELinux, give Red Hat Enterprise Linux a good look, as SELinux has been included since version 4 and will be included on all future releases.
If you're looking to add it to a free distro, it's best to check the Wiki for your individual system before continuing. Installation is not difficult. For example, on Debian, it involved little more than running apt-get, renaming the filesystem, editing the GRUB menu, and starting the system. Instead of providing a long list of instructions for each distro in this article, I've elected to include the links below, which each provide excellent instructions for your specific distro.
Sadly, Yellow Dog Linux is all but devoid of information on installing SELinux, which is probably a good indication that you should look at one of the other distros if you're in need of SELinux.