If you've successfully built libzmq and jzmq in that order, I would run:
$ sudo ldconfig
to update the system library cache. Then I would check to see if LD_LIBRARY_PATH is defined like Raffian mentioned, or set your library path explicitly to something like:
$ java -Djava.library.path=/usr/lib:/usr/local/lib