Following your instructions I get:

./perl_libyaml.h:16:10: fatal error: yaml.h: No such file or directory
 #include <yaml.h>
          ^~~~~~~~
compilation terminated.
[download]

Which I get past by adding "INC" => "-I../LibYAML/include/", to the Makefile.PL. The tests then fail with things like:

#   Failed test 'require YAML::XS;Can't load '/home/marto/code/yaml-li
+byaml-pm/YAML-LibYAML-0.77/blib/arch/auto/YAML/XS/LibYAML/LibYAML.so'
+ for module YAML::XS::LibYAML: /home/marto/code/yaml-libyaml-pm/YAML-
+LibYAML-0.77/blib/arch/auto/YAML/XS/LibYAML/LibYAML.so: undefined sym
+bol: yaml_sequence_start_event_initialize at /usr/lib/i386-linux-gnu/
+perl/5.26/DynaLoader.pm line 187
[download]

I'll do some more digging in the morning.