For MSN Messenger you can't change them normally (if I remember correct), but like john-t suggested, you can replace your sound file with the sound files inside MSN Messenger folder in Program Files folder as long as you modify the name of your custom file as the known names like "online" or "nudge".
But I think you are not using MSN Messenger, but you're using Windows Live Messenger, then you have to go from its menu to "Tools>Options>
Alerts and sounds tab>
Here you can select any sound among the supported types for any kind of alert including Online and New mail alerts.
The path john-t suggested is for Messenger Plus! Live's Event Notifications feature. With this add-on, you can assign specific sounds for your specific contact(s). This add-on requires Windows Live Messenger installed on the system previously, because it is an add-on
I recommend it to you if you are not currently using it.
I am reporting this thread to be moved to MSN/Windows Live Messenger forum
/ 
