Todd: I think it would be cooler if you didn't have to specify what kind of thing your were going to query up front and there were an implicit mapping to class (rather than exposing the table name).

You don't have to specify the thing up front. The following (longer) example creates the query early, then uses the same query object to search an array and to generate SQL.
  query = proc { |t| t.age >= 21 }\n  \n  require 'criteria/array'\n  require 'criteria/sql'\n  include Criteria\n  \n  Person = Struct.new(:name, :age)\n  class Person\n    def to_s()\n      "#{name} (#{age})"\n    end\n  end\n  \n  people = [ Person.new("Jim", 46), Person.new("Dan", 18) ]\n  \n  t1 = ArrayTable.new(people)\n  t2 = SQLTable.new("person")\n\n  puts query.call(t1).select  # Search an array\n  puts query.call(t2).select  # Generate SQL
Output is 
  Jim (46)\n  SELECT * FROM person WHERE (person.age >= 21)
BTW, it looks like Ryan was doing something in this area before our IRC conversation. He credits something called Junction as the inspiration for Criteria.