The following code should accomplish what you want. I've put comments in the Javascript code to explain what i'm doing.
You can take the following code and place it in a blank .html file. It should work fine.
<html>
<head>
<title>Untitled</title>
</head>
<script>
//arrays to contain the names
var males = new Array("Sundin","Mogilny","Belfour"

var females = new Array("Faith","Shania","LeAnn","Womack"
function Populate(name)
{
//if the male option was selected
if(name=="m"

{
//make the menu elements in the name menu equal to the number of names in the male array
document.all["nameList"].options.length=males.length
for(var x=0;x<males.length;x++){
//the text and value of each element will be the name that is in the array
document.all["nameList"][x].text = males[x]
document.all["nameList"][x].value = males[x]
}
}
if(name=="f"

{
//make the menu elements in the name menu equal to the number of names in the male array
document.all["nameList"].options.length=females.length
for(var x=0;x<females.length;x++){
//the text and value of each element will be the name that is in the array
document.all["nameList"][x].text = females[x]
document.all["nameList"][x].value = females[x]
}
}
if(name=="x"

{
document.all["nameList"].options.length=1
document.all["nameList"][0].text = "Choose";
document.all["nameList"][0].value = "Choose";
}
}
</script>
<body>
<select name="gender" onChange="Populate(this.value)">
<option value="x">Select
<option value="m">Male
<option value="f">Female
</select>
<select name="nameList">
<option value="x">Choose
</select>
</body>
</html>