I received a Samsung Galaxy Nexus as a present (in Australia), however I'm not sure where it came from so I'm not sure what mobile frequency bands it supports. Is there a way to check which frequencies it supports so I know which mobile networks I should be looking at?
I don't think there is such option in Android, but if you know your phone's model you could always google it. For instance, if you look at Wikipedia article about Galaxy Nexus, you would see that it supports all four GSM bandwidths (850/900/1800/1900).
Just have a look at "Compatible networks" section in the box on right side.