There are a few ways to generate them, the application may generate them for you or you can use something free like GPGTools (it's for OSX, I don't believe there is a Win version). I'm not up on the latest and greatest for Windows anymore.
You will still need the Public Key of the person receiving the email. So for example if you wanted to send me a PGP encrypted email you can't unless I send you my key first.
Tutanota will keep your emails encrypted on your phone, but unless the other party has sent you their public key the emails sent to them will not be encrypted. I don't know if it will generate a public/private key for you, but I assume it will and also send your public key when you email. If you really want to test it out, create a free Tutanota account and also a garbage gmail account. Then send an email to the gmail account and see what you get. I'm fairly confident the app will generate and store your keys for you (which is another conversation about security) but you again won't have the receivers keys so it's only securing the email content on your phone. Make sense?