For German, in particular, I'd ultimately want to use mnemonics for both the genders (as described in the book), and also for the plural constructions, since they're so random and hard to remember. I'd choose 3 verbs (burning, exploding, whatever) for the genders and then a bunch of people/characters (Albert Einstein, the Queen of England, T-Rex from Jurassic park, etc.) for the different possible plural forms. Then attach them to the nouns as needed.
In terms of priorities, gender is way more important than the plural forms. So as described in the book, mark yourself as incorrect every time you can't recall the proper gender for your nouns.
Plural forms are more in 'bonus point' territory.