ようやく解決！

しかたないので一つづつのコマンドを manで調べて行ったらなんとか解決できました。
gccはコンパイル＋リンクをしてくれる。ここまでは分かっていて、昨日の時点でさらに gccはコンパイルを行ってリンクの処理自体は ldコマンドに投げていたことが判明。ld --helpでラリブラリうんぬんの記述は見つけていたのですが、色々とファイル名を入れたり絶対パスで指定したり試してみたのですが、cannot findと怒られる・・・。なんで？と言った状態で、さらには /etc/ld.so.conf が ldの検索場所との情報もあったので、そこにパスを追加してみたりしたのですがダメでした。
今日そういえばと man ldとしたところ、

-l

19:41+09:00">ar:アーカイブファイル ar をリンクするファイルのリストに加える。このオプションは何回でも指定できる。ldは ar が指定されるごとに、libar.a が見つかるまで検索パスを探す。

libar.a？？？そりゃ、libboost_regex.a を指定してもダメなはずだ orz そんな訳で、boost_regex だけを指定したところ見事にリンクに成功しました・・・。まだまだ linuxの世界は暗黙知で満ちているなと思われた出来事でした・・・。