1:0.1 Gender. Or oh why do the Romans hate us so much?

First of all there is no evidence that Romans thought of their nouns as gendered nor does gender shine any light on the quality of the noun.  It was later scholars decided to group them into two groups, the "a" group and the not "a" group. Then in the 3rd century (according to Loom of Langauge), a scholar decided to call these groups male and female because he was evil. This gendered aspect to the nouns allows you to make connections that in English we have to rely on syntax to make.

Also their are often female versions of the word and male versions, for example "o chafariz" and "a fonte" both can be used to describe a fountain, where fonte can be used as a source while chafariz is just a statue peeing.

So in the main you should study the gender along with the noun. Some people recommend assigning a color to a noun based on its gender in the language. For example take an image of a horse in your mind, now make it blue, and say "o cavalo azul" the male blue horse.  For a female noun image it as a different color, such as red, but this mnemonic trick works best the more effort you put into visualizing the object dressed in it's novel color.

So here are the tendencies of nouns in Portuguese

Female
1) Nouns ending in –ade and –ude are female

A amizade friendship
A universidade university
A juventude youth

2) Nouns ending in –gem are female
A folhagem foliage
A paragem stop
A viagem journey

3) Nouns ending in –ção, -são, -stão, or –gião, which correspond to the English endings
–tion, -sion, -stion, -gion are female, except when they aren't.

A ilustração illustration
A imitação imitation
A nação nation

For example, your heart, seu coração, is male in direct violation of the rule above.

4) Nouns ending in -cie are female

A velhice old age

A planície plain

A superfície surface

5) Lastly, there are invariable female nouns. Always female despite the target not necessily being female. (Remember what I said about groups)

A besta beast, animal
A criança child
A pessoa person
A testemunha witness
A vítima victim

Okay now for "the boys"

As a general rule, nouns ending in unstressed –o are masculine:
O amigo male friend
O carro car
O ano year

Of course there are exceptions
a tribo (tribe)
a foto (photo) This is short for a fotografia

Now, of course, there are male nouns that end in -a
1. Firstly, there are a number of nouns which end in unstressed -a.

O dia day
O planeta planet
O mapa map
O guia guide

2. Nouns which end in stressed –a, indicated by either the acute accent (á) or tilde (ã), are as a general rule masculine.

Some examples are:
O chá tea
O guaraná Brazilian herb and soft drink
O imã magnet
O pá mate, shovel
O sofá sofa
O sutiã brassiere (Br.)
O talismã talisman

Note:
A maçã apple
A lã wool

3. Words which derive directly from the Greek and end in -ma are also masculine:
O drama drama
O diagrama diagram
O programa programme
O clima climate
O telefonema telephone call
O miasma decay
O sistema system


Note, sometimes words end in -ma but aren't Greek.
A fama fame
A chama flame

And then there are the non-Greek -ma nouns that are masculine anyway
O grama  grass

Other masculine noun endings

1. As a general rule, nouns ending in –me are masculine:
O costume custom
O exame exam
O legume vegetable
O lume fire or light

O nome name

O queixume lament
O uniforme uniform
O volume  volume

But, hunger and shame are feminine
a fome hunger
a vexame shame, disgrace

2. As a general rule, nouns which end in –r are masculine:
O andar floor, storey
O ar air
O ardor ardour, passion
O aspirador vacuum cleaner
O colar necklace

O furor fury, rage

O humor humour
O lar home

O mar sea

O motor motor

O prazer pleasure

O par pair, couple

But women in pain with spoons are feminine:
a dor pain
a mulher woman
a colher spoon

3. Nouns which end in –l are masculine:
O anel  ring
O caracol snail
O canil kennel
O casal couple
O fossil fossil
O futebol football
O fuzil rifle
O hospital hospital
O lençol sheet
O mel honey

O painel panel, picture

O papel paper
O perfil profile

O réptil reptile

O têxtil textile

4. Nouns ending in –m are masculine:
O patim skate
O jardim garden
O capim grass

It is basically a toss up, whether  –e, ão and -z endings indicate masculine and feminine nouns

Nouns ending in –e

Masculine
O peixe fish
O cárcere prison
O cheque cheque
O chicote whip
O desfile procession
O envelope envelope
O escritório office
O esmalte nail polish
O ente being
O estresse (Br.) stress
O gabinete office
O limite limit
O leste east
O monte hill, pile
O resgate ransom
O pé foot
O recorte cutting, clip
O sangue blood
O satellite satellite
O traje dress, suit

Feminine
A frase sentence
A tarde afternoon
A frente front
A gafe gaffe
A greve strike (labor)
A lente lens
A massacre massacre
A maré tide
A mercê mercy

Note, o parente, is a false friend in English. It means a relative in the sense of sharing blood but not part of the immediate family:

Masculine nouns which refer to entities of either gender

The following nouns are invariably masculine, but may apply to either gender.
O animal animal
O anjo angel
O cônjuge spouse
O indivíduo individual

Nouns ending in –ão (NOT ção or são) can be masculine or feminine.
Masculine
O avião aeroplane
O escorregão slide but in the falling on your butt rather than the playground kind, which is um escorrega
O pão bread
O travão brake
O trovão thunder
O volcão volcano

Feminine nouns
A escuridão darkness
A escravidão slavery
A mão hand


Nouns ending in –z 

O xerez sherry (this is the town in Spain where the licor comes from)
O arroz rice
O cartaz poster, bill
O xadrez chess

A luz light
A matriz womb, mould
A palidez paleness

Some nouns that change their endings depending on gender

Male Form		English Equivalent	Female Form
O	judeu	Jew	A	judeia
O	europeu	European	A	europeia
O	alemão	German	A	alemã
O	catalão	Catalan	A	catalã
O	Inglês	Englishman/woman	A	Inglesa
O	pai	Father/Mother	A	mãe
O	avô	Grandpa/Grandma	A	avó
O	marido	Husband/Wife	A	mulher
O	espouse	Spouse	A	esposa
O	sogro	Father/Mother-in-law	A	sogra
O	genro	Son/Daughter-in-law	A	genra
O	irmão	Brother/Sister	A	irmã
O	padrasto	Stepfather/Stepmother	A	madrasta
O	primo	Cousin	A	prima
O	tio	Uncle/Aunt	A	tia
O	amigo	Friend	A	amiga
O	rapaz	Boy/Girl	A	rapariga (neutral in Pt, but negative in Br)
O	moço	Boy/Girl	A	moça
O	ator	Actor/Actress	A	atriz
O	embaixador	Ambassador	A	embaixatriz
A	monge	Monk/Nun	A	monja
O	poeta	Poet	A	poetisa
O	juiz	Judge	A	juiza
O	campeão	Champion	A	campeã
O	herói	Hero	A	heroina
O	cidadão	Citizen	A	cidadã
O	rei	King/Queen	A	rainha
O	príncipe	Prince/Princess	A	princesa
O	duque	Duke/Duchess	A	duquesa
O	conde	Count/Countess	A	condesa
O	barão	Baron/Baroness	A	baronesa
O	cavaleiro	Gentleman/Lady	A	dama
O	boi	Bull/Cow	A	vaca
O	galo	Cock/Hen	A	galinha
O	cão	Dog/bitch (In Portugal female dog has no insult value, much like dam in English)	A	cadela
O	Cachorro (Br.)	Dog/bitch (In Portugal these mean puppy rather than adult dog)	A	Cachorra (Br.)

Another group of nouns, referring to profession, status or nationalities are invariable, that is, they don’t change whether the person they are referring to is male or female. Gender is indicated by the definite article o or a or the indefinite article um or uma.

Noun	English Equivalent
o/a artista	artist
o/a burocrata	bureaucrat
o/a cadete	cadet
o/a camarada	comrade
o/a canadense	Canadian
o/a carioca	native of Rio de Janeiro
o/a cliente	client, customer
o/a colega	colleague, classmate
o/a democrata	democrat
o/a doente	invalid, ill person (note this depends on Estar vs. Ser)
o/a estadunense	native of the United States of America
o/a estudante	student
o/a gerente	boss, manager
o/a guia	guide
o/a homicídio	homicide, murdered person
o/a indígena	indigenous person
o/a intérprete	interpreter
o/a jovem	young person
o/a motorista	driver
o/a patriota	patriot
o/a suicídio	suicide
o/a taxista	taxi driver
o/a tenista	tennis player
o/a timorense	native of East Timor

What does it all mean? Basically that over time words have come into Portuguese (looking at you o feedback) and there has been a general agreement into which category to stick the word, but this has been a case by case basis.

At the end of the day build a word list. 500 to 1000 will get you through most situations but the list needs to be tailored to you and your needs. In daily communication it does not matter whether you nail the gender, it becomes more a problem in writing. However, just like spell checker helps with English orthography, changing your computer/phone/tablet settings to Portuguese often (but not always) checks to make sure the genders match.