It does not seem like categories are translated at all during translation of Nynorsk to Bokmål. To make sure a category existed, and was used in both articles, I created the shared category myself. It was still not translated correctly.
The selected category in the left column is properly set up with sitelinks on Wikidata. The item in use is Q7005394.
Language pair is nn-nb, editing from nowiki.
Browser is Firefox 37.0.2 on Ubuntu 15.04.