I’m not a Ruby expert and I don’t have much experience with it, so following steps could be not the best ones, but it worked for me.

First you need to remove jekyll (even all rubygems would be better) and ruby. Les’t start from scratch.

Ruby

Jekyll 3 doesn’t work anymore with version 1.9.3 of Ruby, AFAIK apt-get provide only 1.9.3, so we need to install it using another approach. Here is the list of ways to do it. After several attempts with RVM I’ve chosen ruby-install which was easier for me:

wget -O ruby-install-0.5.0.tar.gz https://github.com/postmodern/ruby-install/archive/v0.5.0.tar.gz
tar -xzvf ruby-install-0.5.0.tar.gz
cd ruby-install-0.5.0/
sudo make install
ruby-install ruby 2.2.4

Then export ruby home in HOME variable:

export PATH="$HOME/.rubies/ruby-2.2.4/bin:$PATH"

Now check the version, should be 2.2.4:

ruby -v
ruby 2.2.4p230 (2015-12-16 revision 53155) [x86_64-linux]

Ruby Gems

This step is as usual, go here: https://rubygems.org/pages/download and follow the instructions (unpack archive, go there and run ruby setup.rb).

Jekyll

Now we need to install jekyll gem and github-pages gems:

gem install jekyll
gem install github-pages

Now you are ready to blog)

In case you use pagination and have following exception while building your site:

Deprecation: You appear to have pagination turned on, but you haven’t included the ‘jekyll-paginate’ gem. Ensure you have ‘gems: [jekyll-paginate]’ in your configuration file.

Add following line to your config.xml:

gems: [jekyll-paginate]