Ubuntu (tested on 14.04) has package called redis-tools which contains redis-cli among other tools.
To install it type:
sudo apt-get install redis-tools
Note that on Ubuntu 16.04+ the command is a little bit different:
sudo apt install redis-tools