Ran into this today which made me scratch my head for longer than it should have:

$ scp file.txt remotehost:~/ 
bash: scp: command not found

But seemingly scp is actually installed fine:

$ which scp

$ scp
usage: scp [-12346BCpqrv] [-c cipher] [-F ssh_config] [-i identity_file]
           [-l limit] [-o ssh_option] [-P port] [-S program]
           [[user@]host1:]file1 ... [[user@]host2:]file2

Not an obvious solution, but scp was missing from the remote machine, not the local one. Quick fix:

$ yum install openssh-clients