I think you may be confused here. Telnet is an old and insecure way of accessing a Linux/UNIX server. The modern equivalent is SSH. The telnet server is not installed by default and I would not install it either. Installed the sshd server instead and access the server with the ssh client.
However, you should note again that this only gives you access to the Linux/UNIX server and not to the database directly.
A standard install of MySQL allows the database to be accessed on port 3306.
I going by this: Backing Up and Restoring Your MySQL Database - MySQL which tells me that I should be able to telnet or SSH into my server and use mysqldump in order to make a backup of my database. If I can't use telnet, I'll have to use SSH I suppose, but SSH doesn't seem to be a recognized command from a standard command prompt. Is it some other keyword? Do I have to download and install SSH?
I'm told that mysqldump will only work through a shell, not through MySQL directly. I certainly know it doesn't work with the latter, so I'm trying to the former.