After some tinkering with the samples, I managed to get it to compile.
The deployment is fine, but it turns out I need to add
LOCAL_SHARED_LIBRARIES := $(ANDROID_MAVEN_PLUGIN_LOCAL_SHARED_LIBRARIES)
include $(BUILD_SHARED_LIBRARY)
include $(ANDROID_MAVEN_PLUGIN_MAKEFILE)
To the app's Android.mk