How do I list all versions of a gem available at a remote site?

Well, it was easier than I thought (well, not really, let's say as easy as it should be):

gem list rhc --remote --all

Which returns:

*** REMOTE GEMS ***
rhc (0.84.15, 0.84.13, 0.83.9, 0.82.18, 0.81.14, 0.80.5, 0.79.5, 0.77.8, 0.75.9, 0.74.6, 0.74.5, 0.73.14, 0.72.29, 0.71.2, 0.69.6, 0.69.3, 0.68.5)
rhcp (0.2.18, 0.2.17, 0.2.16, 0.2.15, 0.2.14, 0.1.9, 0.1.8, 0.1.7, 0.1.6, 0.1.5, 0.1.4, 0.1.3, 0.1.2)
rhcp_shell (0.2.12, 0.2.11, 0.0.9, 0.0.7, 0.0.6, 0.0.5, 0.0.4, 0.0.3, 0.0.2, 0.0.1)

To extend @eyalev's answer, if you want a list of one version per line, here's a one-liner:

gem search '^rspec$' --all \
  | grep -o '\((.*)\)$' \
  | tr -d '() ' \
  | tr ',' "\n" \ 
  | sort
0.0.10
0.1.0
0.1.1
# etc.

To make this a bit more re-usable, you could write some functions (pardon my limited bash skills):

function extract_gem_versions() {   
  echo "$1" \
    | grep -o '\((.*)\)$' \
    | tr -d '() ' \
    | tr ',' "\n"; 
}

function gem_versions() { 
  local gem_name="$1"; 
  local pattern="^${gem_name}$";  
  local vers_str="$(gem search ${pattern} --all)";  
  extract_gem_versions "$vers_str";  
}

gem_versions rspec | sort
0.0.10
0.1.0
0.1.1
# etc.

According to RubyGem's Guide you should use the search keyword. So the command could be:

gem search rhc --all

If you want the exact name use:

gem search ^rhc$ --all

If you want to include prerelease versions use --pre

gem search ^rhc$ --pre

And if you're using zsh add quotes:

gem search '^rhc$' --all