I had trouble installing selinux and getting it to work. The following command:
sudo apt-get install selinux
installed selinux and selinux-policy-dummy. Consequently, selinux was not enabled because of the lack of a policy folder in the /etc/selinux directory. Additionally, during boot, a load_policy file not found error occurred after the init process started. The problem was the _load_policy script in the /etc/initramfs/scripts/init-bottom was pointing to the wrong directory. I changed it from /sbin/policy to /usr/sbin/load_policy and ran the following command
sudo update-initramfs -u -k `uname -r`
Nevertheless, there was no policy in the etc directory. I tried to install "sudo apt-get install selinux-policy-default", which proceeded to uninstall selinux. I appears the selinux on Ubuntu is hosed, and after much dubbing around with this, I decided to install the latest selinux packages from the http://www.debian.org/distrib/packages ( I used Lenny in order to get the next highest version over the Ubuntu version). I installed anything that had to do with selinux. Below is a list of files that I used:
Lastly, I had to change the init program from upstart-compat-sysv to sysvinit to be able to boot selinux
sudo apt-get install sysvinit
Nothing seems to ever go that smooth. After installing sysvinit, I could not gracefully reboot. It would just go back to the login screen. Luckily, I had sysrqd installed, which I allowed me to gracefully sync and unmount the RAID hard drives, then reboot. If you want more info on sysrqd, google it with the "REISUB" keyboard sequence
Note: the audit2allow command from Ubuntu did not work because of the import python-sepolgen error. The import statement should just be sepolgen. Additionally, there was a problem with the python-selinux shared object file. Updating all selinux packages cured this problem. Hence, audit2allow command works fine after upgrade.
Hope this info helps!