LinuxKernel > SELinux
Introduction
SELinux was initially a project to port the work developing a mandatory access control architecture done by the National Security Agency (NSA) and the Secure Computing Corporation (SCC) on the Mach and Fluke OS's to Linux.
For more information please read the NSA SELinux website and a paper on why mandatory access controls are a good and likely a necessary thing.
Debian SELinux support
The Debian packaged Linux kernels have had SELinux support compiled in (but disabled by default) since version 2.6.9. In order to activate SELinux the parameter selinux=1 must be passed to the kernel when booting. Alternatively, you can compile your own kernel with SELinux enabled by default.
The SELinux support is in constant flux, so it is generally recommended that you use an up-to-date installation of unstable if you want to experiment with SELinux (for instance, the Debian packaged Linux kernels did not include "audit" support until version 2.6.13).
In addition to kernel modifications, several user-space application need to be modified to support SELinux properly. Patched versions of these should be in Debian unstable & testing by now.
Debian SELinux wiki pages
There are a number of pages which you might want to read if you decide to experiment with SELinux:
Setup - How to setup your Debian Testing/Unstable system to use SELinux
Issues - Issues currently affecting SELinux support in Testing/Unstable
OldIssues - Issues only relevant to older releases
Notes - Scratch space with some notes about SELinux use and setup
HowToUse - How to work with your SELinux system once it is up and running
Non-Linux Platforms
Please note that SELinux is a Linux-specific feature and Debian packages shouldn't assume it is present (unless they're Linux-specific packages for some reason). Remember to check whether this is a Linux platform by using dpkg-architecture variables in debian/rules, and conditionalise the libselinux Build-Dependency using [] tags. Something like [!kfreebsd-i386 !kfreebsd-amd64 !hurd-i386] should be fine.
External Debian SELinux links
Alioth repository, mainly with backports of SELinux to Sarge.