SELinux (Security Enhanced Linux) offers a more restrictive access control mechanism than normal Unix permissions. The Unix way is called Discretionary Access Control (DAC). File owners, even unprivileged users, have enough control over the files they own to grant unsafe permissions, such as making them world-executable or writable. The superuser has no restrictions at all, which is why privilege escalation is the primary goal of an intruder.
SELinux uses Mandatory Access Controls. Users cannot override these, so it places a great big roadblock in the path of privilege escalation. This makes it a great security tool for servers that face untrusted networks, and perhaps for locking down corporate desktop installations, to prevent user mischiefs.
While this all sounds wonderful, SELinux has acquired the reputation of being too difficult for all but the most security-conscious server administrators. Thus, rather than resolving problems with using it, admins turn it off. Any security device, no matter how wonderful, is no stronger than the person using it. If that person doesn't understand how to make it work correctly, it's not a good security device for them. But is SELinux really so hard? Let's take a look.
Most Linux distributions now offer SELinux-enabled kernels. Red Hat Linux and Fedora Linux have led the way with SELinux; it's included in the default installation, and the user is presented with options to enable or disable it during installation. Red Hat put a lot of work into designing a default policy that protects all kinds of services and applications, so much of the complexity is already handled. Both Red Hat and Fedora also include some nice management utilities, making SELinux even easier to use. You don't need to be a super-guru to set up a workable SELinux policy, just an ordinary, diligent server administrator unafraid to read a bit of documentation.
A great way to get started understanding SELinux is to set up the latest release of Fedora Linux on a test system. Fedora includes many nice management tools. Be sure to study the documentation as well: the SELinux FAQ and the SELinux Wiki.