You need to have Ruby installed. Verify your installation by running ruby -v in a terminal - it should print "ruby 1.9.3" (or higher).
You need to have DevKit installed.
You can get Ruby and DevKit from RubyInstaller.org
Install selenium-cucumber gem by running
gem install selenium-cucumber