You can unpack gems to your Rails application, which will make sure that they are deployed together with your application:
rake gems:unpack:dependencies
Now you no longer have to install the gems on the server you deploy to. This already takes care of most of the deployment issues. Most others are solved by Bundler, which will be included with Rails 3.
If you can, use gems over plugins. Gems are generally easier to manage, because their versioning is superior to plugins. For public Rails extensions, I see no reason to use plugins instead of gems, but some authors only offer one of the two. In that case you have no choice.