Installing Jekyll on Ubuntu 16.04 LTS
After juggling around with Ruby and Jekyll installation packages on Linux, I found a comment being more helpful than the official documentation.
sudo apt-get install ruby-dev
sudo gem install jekyll
After that, I still had one issue:
Yikes! It looks like you don't have jekyll-sitemap or one of its dependencies installed.
sudo gem install jekyll-sitemap installed the required dependency, and everything was working like charm.