I was just involved in a port of a Rules Engine for a top US bank. The engine was written in Smalltalk. To make a very long story short, most of the rule components had a 1-to-1 translation to a Smalltalk code block (or collection of blocks), which was then compiled and executed. This would be a great way to implement a Rules engine in Ruby. Define a very simple language, all of whose components have a 1-to-1 mapping to a small subset of Ruby. Generate the Ruby code and compile it. If your subset is kept simple, you can easily use a compiler-compiler or just hand code a top-down parser. With a strict subset of Ruby, you could also make everything a method and get the s-expression for each method instead of parsing it yourself, but this makes it less straightforward to restrict your subset of Ruby to exactly what you want. (You may want such restrictions if you have non-programmers maintaing the rules.)
The framework I was working with also had components where arbitrary Smalltalk code could be used. In retrospect, this is a bad idea.
All of the rule components were stored as strings with bits of metadata using an Object Relational framework.
Also note that the entire Rules repository only amounted to about 5MB of compressed data. I suspect this isn't unusually small. Rules can be cached locally with the system only checking for updates.
(EDIT: DO NOT naively think you can use a bunch of regexps instead of a parser of some kind. You can make this work, but it's a hack. If you don't know enough about automata and languages to know why this wouldn't work, you probably don't know enough to be certain about the results of such a hack.)