It turned out I was pretty close. I changed f.input to f.association and Rails knew what to do.
It turned my simpleform code into
= simple_form_for user do |f|
= f.association :agency_user_relationships, as: :check_boxes, collection: Agency.all, label: t(:agencies)
= button_tag type: :submit, class: 'btn btn-primary controls' do
= t(:add_agency)
Now, the form shows up with all the Agencies that exist, but the ones which already have relationships with my user are checked by default. The rest is controller code.