Installing Jekyll with gem

sudo gem install rdoc

Then

sudo gem install jekyll

you can see the answer at https://github.com/mojombo/jekyll/issues/762

I'll brave enough to post another answer. I've just installed Jekyll on Ubuntu 12.04, so I hope that this piece of text will save somebody's time.

Firstly, you'll have problems with ruby-1.8.

You should install ruby-1.9 as described here:

sudo apt-get update
sudo apt-get install ruby1.9.1 ruby1.9.1-dev rubygems1.9.1 irb1.9.1 ri1.9.1 rdoc1.9.1 build-essential libopenssl-ruby1.9.1 libssl-dev zlib1g-dev
sudo update-alternatives --install /usr/bin/ruby ruby /usr/bin/ruby1.9.1 400 \
        --slave   /usr/share/man/man1/ruby.1.gz ruby.1.gz \
                        /usr/share/man/man1/ruby1.9.1.1.gz \
        --slave   /usr/bin/ri ri /usr/bin/ri1.9.1 \
        --slave   /usr/bin/irb irb /usr/bin/irb1.9.1 \
        --slave   /usr/bin/rdoc rdoc /usr/bin/rdoc1.9.1

choose your interpreter changes symlinks for /usr/bin/ruby, /usr/bin/gem, /usr/bin/irb, /usr/bin/ri and man (1) ruby

sudo update-alternatives --config ruby
sudo update-alternatives --config gem

now try

ruby --version

Unfortunately, this is not enough. May be some commands here are odd and you can install jekyll without them... But let them be. Maybe somebody will improve my answer.

As of 2016-11-26, jekyll and rdoc required ruby-2.2. Install it as described:

sudo apt-add-repository ppa:brightbox/ruby-ng
sudo apt-get update
sudo apt-get install ruby2.2 ruby2.2-dev
ruby2.2 -v

Then install rdoc and jekyll:

sudo gem install rdoc jekyll

Update alternatives again:

sudo update-alternatives --config ruby
sudo update-alternatives --config gem

Of course, you should choose *2.2

Finally, now you can install jekyll:

sudo gem install rdoc jekyll