It generally starts with what pressures are causing them to want to make contact with the outside world? Generally, depending on the species and their drive, a civilization that is healthy and self-sufficient (and is not being invaded) has no need to reach out to other nations barring general curiosity.
If they are doing this because they need resources, there are two avenues they would have to explore: a) invading nations with resources they need and b) making overtures to nations with resources they need. The former would hinge on an analysis of the military strengths and allegiances of those involved. For example, if your nation had a ridiculously overpowered weapon that could wipe out another country in an instance, I don't think they'll have too much trouble invading. :)
For the second avenue, if they were really trying (and depending on how desperate they were for the resources), they could learn the language and customs of the nation in question and make overtures via a delegation. For example, let's say they need food and they wanted to approach the US (in better times), they could learn the language (listening in to broadcasts, figure out the Internet, etc.) and learn that hands in the air and a white flag are signs of surrender/peace.
If they're doing this out of curiosity or because they've decided to give up on being isolationists, I figure they'd take the peaceful route noted above. Alternately, they might decide to send agents to integrate into the destination society and bring back their knowledge to help adjust to how they need to interface with that society.
In terms of first contact, it depends on who they want to interface with. If we're talking about the rough scenario you outlined above, then interfacing with the UN is probably their best bet since they're looking for an international/all-encompassing relationship with the rest of the world. If they wanted to connect with a single country, then obviously, they'd approach the capital (or perceived capital) of that nation.
A lot of this depends on how well their society syncs up with the target society. Water breathing entities that barely see the light of day might have a LOT of trouble interfacing with those floppy air breathers above. Additionally, if they are drastically different from humans, they will likely need to address that somehow, either by hiding their appearances or finding a way to make themselves look more human, which can lead to some seriously funny but scary situations.
Separate Relations with Nations
Again, depending on their goals and such, they may decide to do separate deals with different nations. From the outside, I'm guessing they'd do it as a sort of common sense diplomatic strategy where they want to establish embassies with various major countries to do business with them. They might start with the UN as a general starter but ultimately the UN is more of a forum than an actual entity you'd entreaty with (most countries don't like giving up their sovereignty which is why we are where we are historically).
Going forward, you'll want to ask yourself some questions about whatever nation this ends up being to help determine how they'd approach this:
- Are they physiologically different and will that cause problems for any relationship they hope to foster?
- What are their motivators/drivers when it comes to opening relations with another country or the world? Everyone and every country has them whether they like to admit it or not.
- What is their technology level and does it work along the same lines as ours? Atlanteans might rely on chemical circuits for their technology or even light because shooting electricity through salt water may not be very effective. :)
- How far or close are they to the target civilization in terms of social norms? They may hate the idea of socializing or conglomerating in crowded conditions because the seas are so vast. Or they might be too clingy for the same reason.