In Ubuntu 10.04 it works out of the box for me. In bash:
$ hg c
cat checkout clone commit copy
Or in zsh:
$ hg c
cat checkout ci clone co commit copy cp
Perhaps you have a package missing (or you hit a bug).
On my system the completion file is provided by the mercurial package:
$ dpkg -S /etc/bash_completion.d/mercurial
mercurial: /etc/bash_completion.d/mercurial