Add a flag to your Collided method, and when you call a pair of Collided events only have one of them process the sound (AUDIBLE and SILENT are simply constants for TRUE and FALSE):
a.Collided(b, AUDIBLE); b.Collided(a, SILENT);
This method is very simple, but it does require that you are calling the events in pairs... in other words, that they are explicitly called right next to each other for each collision. Another method, and this is similar to what @GeorgeDuckett was suggesting, is this:
Regardless of whether you have the sound code external to the objects or inside them, you will be doing a table lookup in the end... asking the sound system if it has a sound that matches objects a and b in either order. Make sure that this query is order independant... it should return the same result for (b,a) and (a,b). If you will not have every combination possible, you should also have failthrough logic... for example, you might have a generic 'a' sound that you use when there is no specific sound for collisions with 'b' (or vice versa, of course).
Both of these suggestions require locality; they require that you are processing both sides of the collision at once. If your code looks like this you will need a different answer:
for each object