I was trying to scp and rsync from a Mac into a brand-new CentOS VM, and was getting this error, even after installing rsync and scp on my remote machine with yum install openssh-clients and yum install rsync:
scp firstname.lastname@example.org:~/whatever.txt ~/
scp: command not found
Same problem with rsync.
It turns out scp and rsync are expected to be on the remote machine at /usr/sbin but are at /usr/bin by default.
Creating symlinks on the remote machine worked for me:
ln -s /usr/bin/scp /usr/sbin/scp
ln -s /usr/bin/rsync /usr/sbin/rsync
For the difference between sbin and bin, see here.