Okay, got it working. After some fight with Neo4j configurations I finally found a solution. It was simpler than initially thought.
In Neo4j manual, it says that all dependencies need to be packed with the jar:
"Having built your code, the resulting jar file (and any custom dependencies) should be placed in the $NEO4J_SERVER_HOME/plugins directory."
The problem is if you need to link a native library. I couldn't find any note on that in Neo4j's manual, apart from the normal Neo4j JVM configurations.
The solution is very simple, you can add the path for any additional library using the java options that you pass to the Neo4j server.
You can do this by editing the file /etc/neo4j/neo4j-wrapper.conf and add the following line:
wrapper.java.additional=-Djava.library.path=/path/to/native-library
Cheers,
Luis