When a theme or plugin adds an image size to the list of thumbnails, they will be added to the global $_wp_additional_image_sizes array. This means that every time you upload an image, any additional image sizes will be generated right after the upload is completed.
The answer to your second question is no. WordPress does not generate thumbnails on the fly. They will all be generated after each upload.
If you are going to add a dozen of image sizes and your blog has a lot of images, I suggest you use a plugin that allows you to organize your upload library, or you can use the code from this answer of mine to do it yourself.