It helps to memorize words in common expressions, not just making up random combinations. For example скорая помощь. Or practice telling stories using the words, or learn songs that employ these words.

Another good way to remember the gender is to think of the instrumental form. For example, лось /с лосем, рожь/ c рожью. лощадь/ с лощадью, конь/ с конем.