"This new cheese is tasty."
Translation:Ten nowy ser jest smaczny.
Generally it's the ending, even if there are exceptions to it. You have to look at the Nominative form, the basic one.
If it ends with a consonant, the noun is most probably masculine.
If it ends with -a, the noun is most probably feminine.
If it ends with -o, -ę or -um, the noun is neuter.
Apart from that, the logic may indicate the gender. Words like "tata" (dad) and "mężczyzna" (a man) end with -a, but as they clearly describe masculine subjects, they are masculine.