How to get coloured terminal over ssh?

Because it was xterm on the server, I figured something was wrong with .bashrc

And indeed! ls --color=auto works only when you are connected to TTY. Changing everything to simply --color in .bashrc on the remote host and everything is in pretty colours now.

This worked for me:

ssh -t my_host my_command

-t was the key. Explained:

-t      Force pseudo-tty allocation.  This can be used to execute arbitrary screen-based programs on a
        remote machine, which can be very useful, e.g. when implementing menu services.  Multiple -t
        options force tty allocation, even if ssh has no local tty.

Seems like colors were already set in ~/.bashrc for me and the issue is that ssh does not use the bashrc file. You can use bashrc in your ssh session by adding the following to ~/.bash_profile:

if [ -f ~/.bashrc ]; then
      . ~/.bashrc
fi