You would make the changes in the skin.css file, changing the styles for the menu classes.
Now, as I haven't done this, I can't tell you which styles to change, but I can tell you how I would go about this. You will need to look at the page source to identify the classes that are used. You can also use Web Developer's Toolbar to identify these. Take a look at
Troubleshooting DotNetNuke Skins to see how to do this.
You will be modifying the properties of links, specifically the hover property, so you may need to look at the page source to see exactly how this is implemented.
It may also be befeficial to switch your menu to something like Snapsis' CSS Nav Menu, as this may be easier to understand and restyle.