SSH uses host keys to authenticate a specific computer in order to ensure that you are not victim of a man-in-the-middle-attack. The host key is usually auto-generated when SSH is installed on a computer, and hence can change if the computer is re-installed (or for some reason the administrator changed it via
An SSH client will create a local database of "known" remote hosts where it stores which SSH host key belongs to which computer, where the computer is identified either by its FQDN or the IP address. In Linux, this is usually the file
.ssh/known_hosts in your user's home directory; under Windows, PuTTY will store it in a registry key. If, upon contact, the host key presented by the remote host does not match the entry in the local database, the SSH client will issue a warning so that you can decide whether you want to continue contacting that computer or not (e.g. because you suspect a man-in-the-middle attack).
Now, upon first contact, the host key of the remote host is not yet stored in your local database. So the client cannot know whether that computer is actually "the right one". It may very well be, so it presents you with an option to trust the key presented and store it as the authoritative authentication for that computer for all further connections (If you trust this host ...). If you know that the host key, as identified by its fingerprint, does correspond to the computer you want to connect to, you can click "Yes" and store the host key in your local database. For all further connections, the SSH client will then check that the host key is still the same, and if it is, no warning will be issued anymore.
The only way to actually "be sure" if the host key is the right one is to contact the hosting provider and ask them to tell you the fingerprint of the computer's host key.
As noted by @Ginnungagap in a comment, there are ways to "publish" SSH host keys like SSHFP records or SSH host certificates, but PuTTY has only recently added support for certificates, and not yet for SSHFP.