Despite the documentation on http://storm.apache.org/releases/1.0.1/State-checkpointing.html it is not enough to simply copy storm-redis-*.jar to extlib to get the RedisKeyValueStateProvider working. Depending jedis and apache-commons-pool2 jars are missing and must be copied by hand to get it working. Else one is greeted with exception stack traces like:
Copying commons-pool2-2.4.2.jar and jedis-2.8.1.jar from hand to extlib solves the issue.
It might be better to create a "fat" jar of storm-redis-*.jar or provide documentation, which libraries have to be made available.