和歌で巫女さんが神託を降ろす、という歌占（うたうら）という習慣が昔の日本にはあったからです。この名残で、「巫女さんが神がかりして和歌で神託を降す」という習慣がすたれた現代でも、多くのおみくじには「和歌」が掲載されているのです。
もともと和歌というのは、スサノオノミコトが31文字で歌を詠んだのが和歌の初め、という伝承があります。「八雲立つ 出雲八重垣 妻蘢みに 八重垣作る その八重垣を」という古事記にも掲載されている和歌がそれです。「神様は和歌を詠む」という話が、遅くとも奈良時代からは存在していたことが推測出来ます。
中世の日本には「巫女が神がかりをして和歌を詠む」という習俗が存在しました。ギリシャのデルフォイの神託ではありませんが、日本の巫女は神がかりして和歌を詠んだのです。これで神意を占う習慣があったのが「おみくじに和歌」があることの歴史的な源です。
室町時代にはじまる能楽では、このテーマを描いた「歌占（うたうら）」というそのままな名前の作品があります。
そして、古い時代には巫女が即興で神がかりして和歌を詠んでいましたが、段々と 「和歌を事前にリストアップしておいて、そこから客に引いてもらって占う」という、易やタロットカードなどに近いスタイルに変化していきます。能楽の歌占では、占ってもらう人は和歌が書かれている短冊をひとつひき、短冊に書かれている和歌をもとに占い師が神意を占うというスタイルになっています。
現代では、神社にいって「巫女さんに神がかりしてもらって和歌を詠んでもらう形で、神意を占ってほしい」と昔の人と同じリクエストをしても、やってくれるところはほとんどないと思います。（神社といっても、いわゆる教派神道、そして神道系新宗教や古神道・復古神道、まで含めて視界を広げれば探せなくはないと思いますが、数としては少ないでしょう）
これはなぜかというと、明治から昭和初期にかけて、多くの神社が政府の統制下に入った時代があります。この時に、「神道は宗教にあらず」とされたため、「占い」のような「いかにもスピリチュアルなジャンル」は神社の仕事内容からは外れていったのだと思われます。
また、現代のお坊さんが書いた本でも「理論が得意な人、呪術が得意な人、法話や説教が得意な人、坊主も人によって得意分野が別れる」という内容の話を読んだことがありますが、占いや呪術というのは属人的な要素が強いスキルであると予想されるため、その手のスキルをもった人が配置されていない場合はやりようがないという面もあるのかもしれません。
明治政府は近代化政策をすすめるために、色んな宗教政策を行いました。「セックスを連想させる祭りは見栄えがわるいから廃止」、「カレンダーに占いを掲載することを禁止」、「実はナンパ祭り状態だった盆踊りを禁止」、などなど、近代化のために色々と風俗の統制を試みていました。その一環で、いろいろと消えていった昔の習慣もあったということです。
ということで、「和歌」が神社のおみくじにのっているのは、昔は和歌でご神託を聞くという習俗があったからなのです。
なので、おみくじの楽しみ方としては「大吉・大凶」というところと「失せ物 よろし」的なところを読むだけでなく、「和歌そのもの」をストレートに解読して「きっと今年は、こんな運勢だろう」と参考程度にイメージしてみるのも楽しいと思います。
追記
このテーマですごく遊べるグッズ（学べるグッズ）を発見したので紹介します。国文学の人の作った歌占いカード、和歌のオラクルカードです。
