CentOSにEPELリポジトリを追加したにもかかわらず
Docker-ioパッケージがインストールできない！なぜだ！
と思ったら、ここに書かれている動作環境に適してなかった！

You will need RHEL 6.5 or higher, with a RHEL 6 kernel version 2.6.32-431 or higher as this has specific kernel fixes to allow Docker to work.

とのこと。
$uname -r してみるとカーネルのバージョンが2.4だった

ということでバージョンを2.6系にしてみたところ
無事インストールできた！