The most secure way is to distribute the server's public key securely by other means. The public key stored on the client is supposed to match that of the server when you connect to it - so if you connect, and then store the public key to verify subsequent connections, you have only guaranteed that you are connecting to the same server each time - and not that it is the server you expect. This is particularly important if you are connecting over the Internet and have reason to believe the server might be compromised.
Practically, most clients display the public key when it is first encountered and leave it up to the user to decide if the public key should be accepted.