Currently, if you add a new Report Category to a Dynamics system, there is no way to get that Report Category into a target system via Solutions. Or, if there is, it is not intuitive or well documented.

If I include a report in a solution, and that report uses a custom report category, the custom report category should be included in the solution and imported into the target environment.