As the company Rails evangelist one of my challenges has been working out a consistent and understandable deployment strategy. One of the biggest challenges is that I may not have access to the root user acct. Additionally we are generally required to stay within the Etch distro, going with Lenny (testing) requires special approval. A final challenge is that compilers are not allowed on the production server.
The "Ruby gem problem" is the result of not having access to the root user acct. On development servers Ruby gems are easily managed using the root acct with the "gem" command. But without root on the production server, how do get our gems installed? Well, you might think we can just request the owner of the root acct to install gems, but not so fast - the gem command does not place files in accordance with the Linux FHS (see http://www.pathname.com/fhs/pub/fhs-2.3.html). And furthermore, the manager of the server has no interest in keeping track of Ruby gems and managing them seperately. If it's not related to "apt", you've got some explaining to do.
So the first thing to do is to avoid the problem as much as possible. Start by freezing Rails into your app, this will eliminate the need for the Rails gem (and dependencies) being installed on the server. This has a beneficial side effect of eliminating any risk that the version of Rails your app needs is not available.
Next identify what gems exist as Debian packages that will work for your app. Some gems are tied to other services on the server (such MySQL) or haven't change in a long time - these are good candidates for install as Debian packages. The downside here is that these gems won't be in the SCM for your project, thus you'll need to make note of these dependencies somewhere for the benefit of future developers.
Finally adopt the "vendor everything" (see http://errtheblog.com/posts/50-vendor-everything) approach and embed app dependency gems directly into your app. By having these in your SCM you're guaranteed that the gem is available to your app, you'll always have the correct version and you have complete control over the version of that gem.
There one last bit to this puzzle. Gems such as Mongrel, Mongrel-cluster and Rake must be installed as system-wide gems. But the Etch versions of them are just too old to be considered. In this case we install them as Debian backports - which works for Mongrel and Mongrel-cluster.