ruby、どうやってインストールしていますか？rvm？それともrbenv？
私はhomebrewを使っています。楽です。
しかしながら、その場合gemの実行ファイルのPATHを手動で設定する必要があります。
PATH=$PATH:/usr/local/Cellar/ruby/1.9.3-p327/bin みたいな感じですね。
これを自動でやるという手もあります(gem の PATH を動的に設定する - すぱぶろ)が、もっと楽かもしれない手段がありました。
brewbygems を使いましょう。
gem installをhookして、/usr/local/bin以下にgem実行ファイルのシンボリックリンクをおいてくれます。楽です。
注意
rubygems.orgにあがっているのは古い(v0.4.0)ので、うまく動かない可能性があります。
githubからcloneして最新版(v0.5.0)をインストールしましょう。
% git clone git://github.com/indirect/brewbygems.git
Cloning into 'brewbygems'...
remote: Counting objects: 104, done.
remote: Compressing objects: 100% (51/51), done.
remote: Total 104 (delta 38), reused 102 (delta 36)
Receiving objects: 100% (104/104), 12.61 KiB, done.
Resolving deltas: 100% (38/38), done.
% cd brewbygems
% rake install #そもそもrake入っているか、PATH通っているかは確認してね
brewbygems 0.5.0 built to pkg/brewbygems-0.5.0.gem
brewbygems (0.5.0) installed
% gem install _任意のgem_