I had the same problem, running Mountain Lion with Ryby 2 installed and being used instead of the standard system ruby.
Previously I added PATH=/usr/local/bin:$PATH to my .bash_profile as a way to make sure stuff installed by homebrew, including Ruby 2, take precedence over some system stuff.
Anyway, in this case I was doing sudo gem install cocoapods
and after a succesful install, when trying a 'pod setup' I would get
-bash: pod: command not found '
so I noticed that cocoapods would install their 'pod' binary not in
/usr/local/bin
but rather in
/usr/local/Cellar/ruby/2.0.0-p247/bin/
So to my .bash_profile I added
PATH=$PATH:/usr/local/Cellar/ruby/2.0.0-p247/bin/
and now cocoapods works like a charm.
sudo? I don't need to do that on my Mac, and just installed and started thepodcommand OK (it wasn't previously installed). This is relevant, since wheregem installputs the execuatbles will depend on user environment, and that will be different undersudosudo