diff --git a/salt/modules/selinux.py b/salt/modules/selinux.py
index <HASH>..<HASH> 100644
--- a/salt/modules/selinux.py
+++ b/salt/modules/selinux.py
@@ -1,5 +1,13 @@
 '''
 Execute calls on selinux
+
+.. note::
+    This module requires the ``semanage`` and ``setsebool`` commands to be
+    available on the minion. On RHEL-based distros, this means that the
+    ``policycoreutils`` and ``policycoreutils-python`` packages must be
+    installed. If not on a RHEL-based distribution, consult the selinux
+    documentation for your distro to ensure that the proper packages are
+    installed.
 '''
 
 # Import python libs
diff --git a/salt/states/selinux.py b/salt/states/selinux.py
index <HASH>..<HASH> 100644
--- a/salt/states/selinux.py
+++ b/salt/states/selinux.py
@@ -17,6 +17,12 @@ booleans can be set.
 
 '''
 
+def __virtual__():
+    '''
+    Only make this state available if the selinux module is available.
+    '''
+    return 'selinux' if 'selinux.getenforce' in __salt__ else False
+
 
 def _refine_mode(mode):
     '''
Don't make selinux state available if selinux module isn't

Also, add notes to top-level docstring explaining that the setsebool and
semanage commands need to be available in order for the module to work,
and note which packages provide these on RHEL-based distros.

Resolves #<I>.