Output of which command used for input to cd

Use dirname:

cd "`dirname $(which program)`"

In bash, I recommend type -p over which. which is an external command and it's tricky at times. You can use sed to remove everything after the final /, or use the special-purpose dirname utility.

cd "$(dirname -- "$(type -p program)")"
cd "$(type -p program | sed 's:[^/]*$::')"

On the command line, if you know that the directory doesn't contain any special characters (whitespace or \[?*), you can omit the quotes. You can also use backquotes instead of one of the $(…) (nesting backquotes is difficult, not worth it here).

cd `dirname $(type -p program)`
cd $(dirname `type -p program`)
cd `type -p program | sed 's:[^/]*$::'`

In zsh, there's a more compact syntax.

cd ${$(whence -p program):h}
cd ${$(echo =program):h}
cd ${${_+=program}:h}

(Yes, that last one is cryptic. It uses the ${VAR+TEXT} syntax on the _ variable, with the value being =program which is equivalent to $(whence -p program).)