Could you please see if something like that works in your case? I'm willing to put some time into this if nobody knows a better solution:
I'm looking forward to hear your feedback ;)!
in app/helper/conditions_builder.rb
class ConditionsBuilder < ActionView::Helpers::FormBuilder
  def multiple_select(collection, possibilities)
    content = []
    id = "#{object_name}[#{collection}][]"
    content << @template.hidden_field_tag(id, "")
    ids = Set.new(self.object.send(collection))
    possibilities.each do |p, label|
      uid = @template.sanitize_to_id("#{id}#{p}")
      checked = ids.include?(p)
      content <<  @template.content_tag("div",
                  @template.check_box_tag(id, p, checked, :id => uid) + " " +
                  @template.label_tag(uid, label))
    end
    return content.join(" ")
  end
end
in app/helper/application.helper add:
def conditions_form(&blk)
  form_for @search, :builder => ConditionsBuilder, &blk
end
In your view you add: (in my case I use haml) 
 - conditions_form do |f|
   - f.fields_for @search.conditions do |s|
     = s.label 'Name'
     = s.text_field 'name_contains'
     = s.multiple_select :state_equals, ['open', 'active', 'gone'].collect{|s| [s, _state(s)]}
     = f.submit _("Search"), :class => 'buttons'
In my case I set some defaults: (not sure if this is the best way to do that):
  unless params[:search]
    @search.conditions.state_equals = ['open', 'active']
  end