you can only package gems that are non-native. There are some things you can do with bundler, but I won't get into that. Checking on the gem, it appears that it has at least one native dependency that I know of - nokogiri. I recommend installing this on the server with:
> sudo gem install feedzirra
This will try to install the gem and all dependencies. You will likely get some dependency errors. Nokogiri requires the libxml2 and libxslt. This tutorial will help you get it installed depending on what kind of server you are deploying to:
http://nokogiri.org/tutorials/installing_nokogiri.html
There are some other dependencies reading up on feedzirra, there are some instructions at http://github.com/pauldix/feedzirra on how to resolve issues with the taf2-curb gem (at least on ubuntu).
I hope this helps! Deploys can be a bear sometimes.