Have you added cucumber to your environment(s)?
From Railscasts.com (#155) as an example. Adjust as you need.
# config/environments/test.rb
config.gem "rspec", :lib => false, :version => ">=1.2.2"
config.gem "rspec-rails", :lib => false, :version => ">=1.2.2"
config.gem "webrat", :lib => false, :version => ">=0.4.3"
config.gem "cucumber", :lib => false, :version => ">=0.2.2"
Cheers,
Chris