What is the proper way to address NCOs in different branches?

When in doubt SGT or Sir are both respectful. They will correct you if you get it wrong. I had troops that switched to Army from Marines. Their conditioning meant that I was called Gunny pretty regularly. I was not offended, I just had to keep reminding them I don't eat crayons.

In the Marine Corps:
E-4s & E-5s are referred to as Cpl or Sgt
E-6s are referred to as Staff Sergeant
E-7s are Gunnery Sergeants but, if they if they allow, you can call them Gunny.
E-8s are either 1st Sergeants or Master Sergeants. At the co level the 1st is usually the senior enlisted and may be called Top.
E-9s are either Sergeants Major or Master Gunnery Sergeants. A SgtMaj is referred to as "Your Holiness" and a Master Gunnery Sergeant is referred to as "Your Majesty" with the appropriate bow rendered!

In Vietnam at 35 years of age I was one of the older First Sergeants in the Battalion. I was aware that even the Battalion Officers called me "Pops" behind my back. Secretly I kind of liked receiving the questionable respect for my age but had anyone said it to my face I may have invited them out behind the "hooch" for lessons in etiquette. When I worked closely with troops long hours of the day I had no qualms about being call Top or Sarge. It is easier and shorter than the title of First Sergeant therefor more efficient. I expected Officers and NCOs senior to me to call me by my rank as I did them when I addressed an Officer or NCO that was my senior. I think judgement of each situation is called for rather than written rules or regulations. Sometimes rigid rules can cripple a unit and prevent good judgment from prevailing.

In the Navy between E-6 and below on ships anyway it was last or nickname, we didn't say "hey leading petty officer" And E-7-E9 was their rank, CHIEF, SENIOR CHIEF, MASTER CHIEF, mostly but often their rank and last name. Now if you heard someone calling you by your rank and last name, that usually wasn't a good thing. Heard a sea-story once about an Ensign & a Master-Chief, supposedly, the Master -Chief was at a shore station eating lunch at an outside patio with some others, when he stood up and started walking away an Ensign walked up to him and said "Excuse me Master-chief but I believe you owe me a salute." to which the Master-Chief replied by taking a Quarter out of his pocket and flipping it to the Ensign "Here's a Quarter go tell you momma you met a real Sailor." Did it happen??? I don't know I wasn't there. Does it sound like it could have happened? Yes I can see this easily happening. It's funny when you think about addressing Officers, you can address them by rank or rank and last name, but a Lieutenant is almost always L.T. and of course in the Navy the CO. is always addressed as Captain regardless of his actual rank.

Navy is petty officer or chief/Sr chief/Master chief

By rank for Marine Corps. I did not like "top" Master Sergeant worked for me

Not really the answer to this question, but the following should shed light on how things really are:
The Image of Rank

General:

Leaps over tall buildings in a single bound, is more powerful than a locomotive, is faster than a speeding bullet, walks on water, and gives policy to God.

Colonel:

Leaps over short buildings in a single bound, is more powerful than a switch engine, is just as fast as a speeding bullet, walks on water if sea is calm, and talks to God.

Lieutenant Colonel:

Leaps over short buildings with a running start and a favorable wind, is almost as powerful as a switch engine, is as fast as a speeding b-b, walks on water in an indoor pool, and talks to God if special request is approved.

Major:

Barely clears quonset huts, loses tug-of-war with locomotives, can fire a speeding bullet, swims well, and is occassionally addressed by God.

Captain:

Makes high marks when trying to leap buildings, is run over by locomotives, can someimes handle a weapon without inflicting self-injury, can doggie-paddle, and talks to animals.

First Lieutenant:

Runs into buildings, recognizes locomotives two out of three times, is not issued ammunition, can stay afloat if properly instructed, and talks to water.

Second Lieutenant:

Falls over doorsills when trying to enter buildings, says "look at the choo-choo," wets himself with a water pistol, and mumbles to himself.

CADET:

UNAUTHORIZED TO DO ANY OF THE ABOVE WITHOUT RTO/BTO APPROVAL, BUT BE READY TO ASSUME THE JOB OF GENERAL IN A HEARTBEAT.

An NCO:

Lifts building and then walks under them, kicks locomotives off the track, catches speeding bullets in his teeth, and chews them, and freezes water in a speeding glance. He is God.

In the USAF if you don't know the individual, you would address them by their rank. Tech Sergeant Smith, etc... Once you know them and have a rapport, you could call them by their first name unless in a formal function... Then stick to rank to keep it professional.

Boot camp is entirely different. Using rank is always appropriate. Other "nicknames" like Gunny or Top are also OK.

When in the Air National Guard, as a Chief Master Sergeant, I was always called Chief. Because I was in fire protection as fire chief of my department, I was 2 or 3 times called Chief, Chief, which I kind of got a kick out of.

A Marine Gunnery Sergeant typically likes to be called Gunny. Other senior MC ranks like the full title, ie: Master Sergeant, Master Gunnery Sergeant. Army senior NCOs are called Sergeant until they make 1st Sergeant or Sergeant Major. Never address an Army NCO as Sarge. He was Beetle Bailey's NCOIC/Platoon Sergeant. Air Force differs by individual but most should be addressed by full rank until they tell you differently. Navy senior NCOs are Chief, Senior Chief and Master Chief.

NCO's are addressed by rank and name. For example, in the Army and USMC, an E-5 and E-6 would both be addressed as Sergeant, even though the E-6 is a Staff Sergeant. The only time I ever heard "Staff Sergeant" used was in a more formal setting or when a superior was upset with the SSG's performance. An Army E-7 is a Sgt. First Class, but addressed as Sergeant, whereas a Marine E-7 is a Gunnery Sergeant or Gunny.

Air Force ranks use Airman and Sergeant, although I have never been comfortable trying to figure out their Sergeant structure. Navy and Coast Guard - I haven't a clue; sometimes I wonder if they even use rank except for decorations. Honestly, though, there is a specific etiquette for each service; don't be afraid to ask. But outside of Boot Camp, the reference "Sir" applies to officers only.

By their rank.

My Marine rank is Cpl, I got it at my 25th month in Service. I was in the Air Wing. Things were much more lax than in the rest of the Marine Corps. Pretty much everyone was addressed by the first name or nickname, whether they were Pvt or SSgt. Everyone above SSgt was call by their rank.
Post Marine Corps, I served in the Air Force. I retired as a Senior Master Sgt. I was either addressed as Sgt, Senior or Sir by junior Airmen. Fellow Airmen that were SSgt and above and I had served with for many years; first name basis.

In marine Boot camp wheb the Drill instructors tell the recuirts something the answers is yes sir. or sir yes sir.

however a army e4 should refer to a Marine gunnery sgt as gunnery sgt or gunny.

While I was in the Navy (over 30 years ago), it was perfectly fine to refer to all Chief Petty Officers as "Chief" omitting their Rating. Alternatively, you could refer to them as Chief, Senior Chief, and Master Chief as applicable. All other Navy NCOs (E-4 thru E-6) could and generally would be addressed as "Petty Officer" without their Rating or specific Rank. Use of the specific Rank was generally reserved for more formal situations such as commendations, reviews, or discipline. Use of the Rating was not generally used very much. I.e., Petty Officer Lastname or just Petty Officer - used most often, Petty Officer 2nd Class Lastname - used rarely, Electronic Technician 2nd Class Lastname - almost never used outside of records.

In the Marines we called an E-7 Gunny and so on up the line. I do not know when the rank was created. During WW11 a Gunny was called a Gunnery Sargent, He was usually over a gun crew. On occasions he could be a mean bastard, that's according to my dad when he was in the Corps.The lower ranks always call the person by his rank and then his last name.

By the rank on their collar, but some marines that I met were offended when I didn’t call the Staff SGT even though I was a SFC and had to tell him to chill out I didn’t mean anything by it. Remember this was in the early 90s.

I've always had the question of what to call a Marine Corps Warrant Officer in conversation with that person. We use Mr and Chief in the Army, what about the USMC for WO1 (Mr in the Army) and beyond, (Chief in the Army).

Each service is so very unique, if you ever have the opportunity of working in a multinational organization it will get even more confusing. Germans, British, Turkish, and all the other countries use unique rank styles and titles. Nice to see that you are taking an interest so as to render the proper respect to these service memebers.