Correct way to customize modules? When making changes to files in sites/all/modules/moduleidownloaded where should the changes be stored? I know you shouldn't edit the core module files for risk of updates etc. So where should I put customized module files such as templates and styles?
You can create two folder contrib and custom inside sites/all/modules. Drupal is able to look up any folders inside sites/all/modules to discover the modules.

If it is multiple site structure, you can do the same in sites/[site_name]/modules

For the custom templates and styles, if you means the theme one, you can place the theme in sites/all/themes/custom, otherwise, templates and styles can be placed inside custom module.