Which version of Ruby are you using?
If it's not 1.9.x, try loading rubygems first

require 'rubygems'
require 'spreadsheet'

-- 
cheers,
junegunn choi.