Could you provide a reproducer please? It seems to work for me:

$ cat test_libselinux.c 
#include <selinux/selinux.h>

int main() {
        return is_selinux_enabled();
}

$ gcc -static test_libselinux.c `pkg-config --static --libs libselinux`

$ ./a.out 

$ echo $?
1

git clone http://github.com/karelzak/util-linux.git
cd util-linux
./autogen.sh
./configure --enable-static-programs --with-selinux

make mount.static V=1

gcc -std=gnu99 -fsigned-char -fno-common -Wall -Werror=sequence-point -Wextra -Wmissing-declarations -Wmissing-parameter-type -Wmissing-prototypes -Wno-missing-field-initializers -Wredundant-decls -Wsign-compare -Wtype-limits -Wuninitialized -Wunused-but-set-parameter -Wunused-but-set-variable -Wunused-parameter -Wunused-result -Wunused-variable -Wnested-externs -Wpointer-arith -Wstrict-prototypes -Wimplicit-function-declaration -I./libmount/src -O2 -g -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -fexceptions -fstack-protector-strong --param=ssp-buffer-size=4 -grecord-gcc-switches -m64 -mtune=generic -fno-diagnostics-show-caret -static -o mount.static sys-utils/mount_static-mount.o  ./.libs/libcommon.a ./.libs/libmount.a /home/projects/util-linux/util-linux/.libs/libblkid.a /home/projects/util-linux/util-linux/.libs/libuuid.a -lrt -lselinux -lsepol -lpcre

...
/usr/lib/gcc/x86_64-redhat-linux/4.9.2/../../../../lib64/libselinux.a(load_policy.o): In function `selinux_mkload_policy':
(.text+0x310): undefined reference to `lzma_stream_decoder'

..etc.

I'm not sure, maybe I blame sepol/selinux incorrectly (I don't see anything related to lzma in libselinux code), but the gcc message is obvious.

If I compile --without-selinux (and gcc command line contains only -lrt) then all works as expected.

Note that the code uses selinux_trans_to_raw_context(), getfilecon(), security_get_initial_context(), selinux_file_context_cmp().

It's related to this [1] commit which apparently hasn't been upstreamed.

[1] https://github.com/fedora-selinux/selinux/commit/890c74c1295ee711796781d9e11e6f7a546bda07

http://koji.fedoraproject.org/koji/taskinfo?taskID=9540099

This is a scratch with reverted commit 90c74c1295ee711796781d9e11e6f7a546bda07. 
But static builds are still broken due to #1214494:

/usr/lib/gcc/x86_64-redhat-linux/5.0.1/../../../../lib64/libpcre.a(libpcre_la-pcre_jit_compile.o): In function `sljit_generate_code':
(.text+0x6b1): undefined reference to `pthread_mutex_lock'
/usr/lib/gcc/x86_64-redhat-linux/5.0.1/../../../../lib64/libpcre.a(libpcre_la-pcre_jit_compile.o): In function `sljit_generate_code':
(.text+0x7a6): undefined reference to `pthread_mutex_unlock'
/usr/lib/gcc/x86_64-redhat-linux/5.0.1/../../../../lib64/libpcre.a(libpcre_la-pcre_jit_compile.o): In function `sljit_generate_code':
(.text+0xb31): undefined reference to `pthread_mutex_unlock'
...

libselinux-2.3-9.fc22 has been submitted as an update for Fedora 22.
https://admin.fedoraproject.org/updates/libselinux-2.3-9.fc22

libselinux-2.3-9.fc21 has been submitted as an update for Fedora 21.
https://admin.fedoraproject.org/updates/libselinux-2.3-9.fc21

Package libselinux-2.3-9.fc21:
* should fix your issue,
* was pushed to the Fedora 21 testing repository,
* should be available at your local mirror within two days.
Update it with:
# su -c 'yum update --enablerepo=updates-testing libselinux-2.3-9.fc21'
as soon as you are able to.
Please go to the following url:
https://admin.fedoraproject.org/updates/FEDORA-2015-6771/libselinux-2.3-9.fc21
then log in and leave karma (feedback).

libselinux-2.3-9.fc22 has been pushed to the Fedora 22 stable repository.  If problems still persist, please make note of it in this bug report.

libselinux-2.3-9.fc21 has been pushed to the Fedora 21 stable repository.  If problems still persist, please make note of it in this bug report.