What does Mare Nostrum mean in Latin?

Mare Nostrum, a proper noun, means “Mediterranean Sea (the sea between Europe and Africa)”.

What is the genitive of Mare Nostrum?

The genitive singular is Maris Nostrī. Mare Nostrum is third declension.

In classical Latin, [ˈma.rɛ ˈnɔs.trũː]; in ecclesiastical (church) Latin, [ˈmaː.re ˈnɔs.trum].

proper nounthird declension

Mare Nostrum n sg (genitive Maris Nostrī)

Classical[ˈma.rɛ ˈnɔs.trũː]Ecclesiastical[ˈmaː.re ˈnɔs.trum]

neutersingularMediterranean Sea (the sea between Europe and Africa)
[…] multīs gentibus eōrum dēductīs illō ā Tigrāne Magnō, sponte vērō ad mare nostrum lītusque Aegyptium […][…] many of their tribes having been brought to that place by Tigranes the Great, but [some having come] willingly to the Mediterranean and the Egyptian coast […]79 CE, Pliny the Elder, Naturalis Historia, vi, 47 (alt. 32)
Orosius’ History Against the Pagans Aegyptus inferior ab oriente habet Palaestīnam, ab occasū Libyam, ab septentriōne mare Nōstrum...Lower Egypt has Palestine to its east, Libya to its west, the Mediterranean to its north...

Literally, “Our Sea”.