Is it good practice for a module to add fields to a certain content type? I have a content type of "album" that is used for displaying reviews of music albums. It has fields like "artist", "genre", "publication_date", etc.

I also have a supporting module that displays relevant albums (that can be purchased elsewhere) for this content type using a 3rd party web service. This module requires a few extra values, like the limit of the relevant albums to be displayed, or a unique id for the artist for the web service.

Is it a good idea to have the module add these extra fields at installation time?
Not only is it a good idea, it is the result of the generally recommended workflow when working with custom content types. If you have other business logic that depends on those fields, I would definitely make them available at install time to make deployment painless.

The Features module can be used to export fields, content types and other configuration into a separate module for you to download, so you do not have to write this yourself. By exporting your configuration to code, it becomes possible to check it into revision control, providing the basis of more complex Drupal modules and distributions.

The KIT specification referred to by Letharion provides a standard for how feature modules (those exported by Features) should be structured for maximum interoperability and portability, but it is the Features module that does the heavy lifting (note, however, that modules created by Features do not name Features as a dependency). Obviously, not every feature you create has to be KIT-compliant, though it does provide a good starting point with a series of sane best practices.

Whether it makes more sense to simply modify the feature module (it is a module like any other, after all!) or make it a submodule of another project depends on the specific use case. If I understand yours correctly, both your supporting module and your content type are used in conjunction to satisfy the same single use case, so I would consider merging them together. Generally, you would make the feature module stand-alone if it could be used independently and satisfies some use case on its own, which does not appear to be the case.

If you have any questions, I would be happy to clarify my answer.