最初に書いていたコード

<%= link_to  controller: "shops", action: "index", q: { name_cont: '東京'}, class: "反映させたいクラス" do %>
 <div>このdivをクリックしたら「東京」の検索結果にとぶ</div>
<% end %>

こちらを参考に書きました。やってることはほぼ同じで、リンクテキストを踏ませるかdivを踏ませるかの違いです。
リンクテキストを指定する代わりにdo endで囲んでブロックにし、controller: ~ 東京 }までがパスで、その後にclassを書いているというイメージです。

エラーは出ずリンクは機能するものの、classが反映されず...

うまくいったコード

<%= link_to ({ controller: "shops", action: "index", q: { name_cont: '東京' }}, { class: "反映させたいクラス" }) do %>
 <div>このdivをクリックしたら「東京」の検索結果にとぶ</div>
<% end %>

最初に書いていたコードも文法的には間違いではないそうですが、classとパスの境目が曖昧でclassもURLの一部と見なされていたようなので、URL部分とその他の部分でハッシュを分けたらうまくいきました。