クイックまとめ
ポルトガル語のすべての名詞に性がある（男性か女性）
-o の語尾＝たいてい男性（o livro, o carro）
-a の語尾＝たいてい女性（a mesa, a casa）
冠詞は一致させる: o/um（男性）、a/uma（女性）
形容詞も一致させる: gato preto, gata preta
-a でも男性の語がある: o problema, o dia
-o でも女性の語がある: a foto, a moto
ものにも性がある（テーブルは「女性」、本は「男性」）
なぜ大切か？
性はポルトガル語の背骨です——あらゆる文で使う冠詞や形容詞、さらには過去分詞の形まで決めます。バーで「um cerveja」とは注文できませんし（正しくは「uma cerveja」）、「a amigo」とほめることもできず（正しくは「o amigo」）、「o problema está resolvida」とも言えません（正しくは「resolvido」）。朝のコーヒー（男性！）からおばあちゃん（女性！）まで、一つひとつの名詞が性を持ち、周りの語に影響します。早いうちに慣れてしまえば、ブラジルポルトガル語の残りの部分もすっと腑に落ちはじめます。
掘り下げ解説
性の基本システム
ポルトガル語の名詞は「男性チーム」か「女性チーム」のどちらかに所属していると考えてください——中立のチームはなく、どの語も必ずどちらかを選ばなければなりません！文法上の性を持たない日本語と違い、ポルトガル語では「テーブル」がいわば「（女性の）テーブル」になります。誰かがテーブルは女の子だと決めたからです。
黄金ルール
ルール1: -o＝男性（ほとんどの場合）
o livro（本）
o carro（車）
o menino（男の子）
o gato（オスの猫）
um telefono（電話）
例文
カフェで
「Um café e uma água, por favor」（コーヒー1つと水を1つ、お願いします）
「O bolo está gostoso」（ケーキはおいしい）
「A conta, por favor」（お会計をお願いします）
「Você tem um cardápio?」（メニューはありますか？）
買い物
「Quanto custa o sapato?」（その靴はいくらですか？）
「A camisa é bonita」（そのシャツはかわいい）
「Eu quero um presente」（プレゼントが欲しい）
「A loja está fechada」（店は閉まっている）
よくある例外
-ão の語尾
-ão で終わる語は -o/-a の規則に当てはまらず、独自のパターンに従います:
-ão の具体名詞はたいてい男性: o limão（レモン）、o mamão（パパイヤ）、o coração（心臓）、o pão（パン）
-ção / -são / -ssão の抽象名詞はほぼ必ず女性: a ação（行動）、a canção（歌）、a decisão（決定）
意味が変わる語
性によって意味が変わる語があります:
o cabeça（リーダー）と a cabeça（頭）
o capital（資本・お金）と a capital（首都）
o rádio（ラジオ機器）と a rádio（ラジオ局）
o grama（グラム）と a grama（芝生）
豆知識
「o problema」はどこから来たのか？
problema、sistema、tema、programa、drama、idioma のような -ma で終わる語は、古代ギリシャ語からラテン語に借用され、ラテン語では文法上の中性名詞でした。ロマンス諸語でラテン語の中性が男性と女性に吸収されると、ポルトガル語はこれらのギリシャ語由来の借用語を男性に振り分けました——だから今日では「a problema」ではなく「o problema」なのです。男性名詞の o dia（日）は事情が異なり、今は -a で終わりますが、男性名詞だったラテン語の dies にさかのぼります。
出典: ポルトガル語の文法（Wikipedia）。
ポルトガル語にはかつて3つの性があった
古典ラテン語には男性・女性・中性という3つの文法上の性がありましたが、中性は俗ラテン語とそのロマンス諸語の子孫の中で次第に消えていきました。ポルトガル語は2つだけを受け継いだので、現代のあらゆる名詞はどちらかを選ばなければなりません。古いラテン語の中性複数形の中には、ポルトガル語で女性単数として生き残ったものさえあります（例: ラテン語の中性複数 folia に由来する a folha「葉」）。