Magentoをスマートフォン対応するには2通りのアプローチがあります。

  • スマートフォン専用テーマをベースにカスタマイズする
  • レスポンシブテーマを導入してカスタマイズする

どちらも一長一短ですが、どう違うのか見ていきましょう。

スマートフォン専用テーマをベースにカスタマイズする

Magentoには比較的初期からスマートフォン用のテーマが付属・無償配布されてきました。
もちろん、サードパーティ製のテーマも数多く配布・販売されています。
この方法の良いところは、

  • 既存サイトのテーマに影響をあまり与えずに導入ができる
  • PCでIE6/7対応が必須（いまさら感がありますが）である場合に有効
  • スマートフォンでPCサイトを閲覧したいユーザーには切り替えリンクを提供できる

というところでしょう。
反面、悪いところとしては、

  • PC用と別にテーマを作成する必要があるため、手間がかかる
  • PC用とスマートフォン用の両方で正しく表示されるようにCMSページなどは調整が必要になる 
  • マークアップが異なるので、検索エンジンにマイナス評価をされることがある
  • スマートフォンサイトへの導線を何処かに用意しないといけない
  • スマートフォン（特にandroid）のデバイス判定処理が必要になる

ということがありえます。
長所短所ありますが、やはり既存サイトが完成している状態で、大きくデザイン変更ができない状況下においては、スマートフォン専用テーマを導入するほうが、作業ボリュームは少なくなると思います。
ですが、PCサイトより商品情報などのコンテンツで差異をつけてしまった場合、検索エンジンに良い評価を得られないことがありえるので注意が必要です。 

レスポンシブテーマを導入してカスタマイズする

こちらは最近様々なCMSで対応が進んでいる方法です。
IE6/7の対応が不要で、かつIE8もあまりアクセスに占める割合が低い場合には選択肢になりえます。

この方法の良いところは、

  • PCとスマートフォンの両方を同じマークアップで処理できる
  • 検索エンジンにとっては同じHTMLなので同一に評価される
  • アクセスしてくる端末に合わせた最適な表示ができる
  • デバイス判定は不要（画面サイズのみで判定）

というところでしょう。
反面、悪いところとしては、

  • CSSとJavascriptで表示の制御をするため、ページ全体のサイズが大きくなる
  • 特にCSSのファイルサイズが肥大化しやすい
  • 既存サイトに導入する場合はPCサイトのデザイン変更が必要になる（場合がある）
  • IE6/7/8に対する対応には多少手間がかかる 

ということが言えます。
スマートフォン専用テーマを導入する場合と同じく、それなりに良し悪しがあります。 

ではどちらが良いのか？

これは一概に言えません。
導入・構築するサイトの性質によって、現状の分析やコスト・期間を考慮して判断しなければなりません。
安易に「別で」「レスポンシブで」という判断を下してはいけないと思います。 

レスポンシブ対応のMagentoテーマとは？

スマートフォン専用テーマは、Magentoの場合標準テーマが付属しますので、それを使うのが手っ取り早いでしょう。
（とはいえ、標準テーマのCSS定義を見なおさないと使えませんが・・・）

反対にレスポンシブ対応のテーマは有料のものが多く、無償のものは比較的少ないです。
今回はその中で使えそうなものを3つご紹介します。

GPMD

GPMD

GPMDはGithub（https://github.com/gpmd/magento-responsive-theme）で配布されているテーマです。
比較的装飾が少なく、シンプルな見た目をしています。 

Mobile shoppe

mobile shoppe

mobile shoppeはMagento connect（http://www.magentocommerce.com/magento-connect/mobile-shoppe-a-responsive-magento-theme-1032.html）で配布されているテーマです。Magento connectからインストールできるので、導入しやすいテーマといえるでしょう。
こちらも装飾は少なめ。ただ、商品詳細ページの画像の表示にやや難があるようなので注意が必要です。 

Bootstrapped

bootstrapped

bootstrappedはCSSフレームワークのBootstrapをベースにしたテーマです。
デモサイトとGithubのページ（https://github.com/vsubotic/bootstrapped）が別になっているのでダウンロードの際は注意が必要です。
かなり完成度は高いですが、Bootstrapで使用しているCSSやJavascriptを使用するため、ページサイスがやや大きくなりがちです。 

商用のテーマもThemeforestなどで多くリリースされているので、うまく使えば少ない作業量で、レスポンシブなMagentoサイトが構築できるでしょう。