How do I set $PATH such that `ssh user@host command` works?

As grawity said, ~/.bashrc is what you want, since it is sourced by non-interactive non-login shells.

I expect the problem you're having has to do with the default Ubuntu ~/.bashrc file. It usually starts with something like this:

# If not running interactively, don't do anything
[ -z "$PS1" ] && return

You want to put anything for non-interactive shells before this line.

Do you have an ~/.bash_login or ~/.bash_profile?

Bash in interactive mode checks for these files, and uses the first existing one, in this order:

1. ~/.bash_profile
2. ~/.bash_login
3. ~/.profile

So if you have an ~/.bash_profile, then whatever changes you do to ~/.profile will be left unseen.

Bash in non-interactive mode sometimes reads the file ~/.bashrc (which is also often source'd from the interactive scripts.) By "sometimes" I mean that it is distribution-dependent: quite oddly, there is a compile-time option for enabling this. Debian enables the ~/.bashrc reading, while e.g. Arch does not.

ssh seems to be using the non-interactive mode, so ~/.bashrc should be enough. When having problems like this, I usually add a few echo's to see what files are being run.

ssh documentation says:

If command is specified, it is executed on the remote host instead of a login shell.

which is why adding to the bashrc files doesn't work. you do however have the following options:

1. If the PermitUserEnvironment option is set in the sshd config, you can add your PATH setting to ~/.ssh/environment

2. ssh remotemachine 'bash -l -c "somecommand"'