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

Address him as Gunnery Sgt! If he was Air Force then it would be Master Sgt or First Sgt, depending on the position. If they are Navy, then Chief or Chief Petty Officer. I worked JTF many times in my career, and I highly recommend studying the rank structure and insignias of the other branches. The first time I addressed a Navy Commander properly based on his sleeve stripes, my life went from Hell to Heaven, especially when I found out he was going to be my new boss. Some will call it kiss ass, I call it cover ass!

I liked to be call by my first name"chief"

In basic training (boot camp) everyone is "sir" or "ma'am". After that, the only time you'd address an E-7 (Gunnery Sergeant) as "Sir" is if he is holding a command position that is normally held by an officer....however, being raised by a Marine, if someone who out-ranks me is yelling at me, it's "Sir" or "Ma'am" no matter their rank ;-) Usually we'd address him as "Gunny".

If you know, then call them in the form that would be courteous to them - as many have illustrated here.

I did have one incident where I was outproccessing from a school at Ft. Huachuca and the mail room was in the Marine barracks. I addressed the Staff Sergeant at the front desk as "Sergeant," as we would in the Army. The PFC that was on duty with him started to dress me down for not addressing him properly. The Staff Sergeant "very strongly" corrected the PFC for being disrespectful to an NCO from another service who obviously didn't know better.

Quick story, I was an AF Independent Duty Medic assigned to a Aid Station that took care of US folks at a NATO base-anyway an Army Sgt Major showed up for my sick call with something in his eye, said it hurt like hell. I said "no problem sir, I'll fix you right up" -anyway after getting the worst ass chewing of my life (I was a Air Force MSgt) I took care of his eye & never called any enlisted Army folks sir. Oh yeah, his boss a Major called to apologize, I told him it was my fault.

With fear and trembling?

I'm a retired Marine who retired at the grade of MSGT. In the Corps, recruits have customarily addressed anything above whaleshit at the bottom of the sea as "Sir" or "Ma'am." After they put on the EGA, they address all officers as "Sir/Ma'am" and other enlisted Marines (especially NCO's/SNCO's) by their correct rank title. As mentioned elsewhere, Gunnery Sergeants and Master Gunnery Sergeants can be addressed by less formal titles (Gunny/Master Gunny) if they allow it. Staff Sergeants are always addressed as "Staff Sergeant" and never as "Staff" or "Sergeant." Master Sergeants can be addressed as "Top" when they allow it. NEVER address a First Sergeant or Sergeant Major by anything but their full title. We used to address our Sergeant Major as "Sir" out of respect. Sometimes it was appropriate to address an NCO/SNCO in formal settings as "Sir/Ma'am," such as when they were acting as Officer of the Day while on guard duty, or in a parade setting ("Take your post, Sir.") . When I was Sergeant of the Guard at Marine Barracks, my sentries would address me as "Sir," which was acceptable as a formal way of showing respect. It used to be customary to address junior company officers and warrant officers as "Mister" (if working in frequent/close proximity). That seems to have passed away, however. It used to be that Marine warrant officers/chief warrant officers would be addressed as "Gunner," despite not being Marine Gunners. Now that the rank of Marine Gunner has been revived, that seems to be going away. We customarily referred to USMC captains in command as "Skipper" (although not generally to his/her face, or in formal settings). Lieutenant Colonels can informally be addressed as "Colonel," and general officers as "General" (no matter how many stars). As to the other branches, I'm most familiar with the Navy, so I generally call non-rates by their last name, petty officers as "Petty Officer" and chiefs by their proper full title. Lieutenant Commanders can be called "Commander" and LTJG's are "Lieutenants."

Marines do NOT address NCOs or Staff NCOs as sir, who told you that nonsense? A Corporal is addressed as Corporal, all other Sgt levels are addressed as Sgt except a First Sgt or a Sgt Maj and they are addressed as just that. An E-7 may be addressed as Gunny by tradition. At least that was the case when I was on active duty pre-Obama, hell, who knows what may be the case now.

E-4 - E-6, 'Petty Officer'
E7 - 'Chief'
E8 - 'Senior Chief' or 'Senior'
E9 - 'Master Chief'. That's it. Just 'Master Chief.' Do NOT EVER call one 'Master', even though you can call E8's 'Senior'.

Gunnery SGT for E7 and you better say it LOL

The Air Force folks always used to call me sir, I told them "you can call me Senior Chief..." They said "Ok Sir..." I was like WTF, but you know it is still a sign of respect... Chief, Senior Chief, Master Chief! 789!

When in doubt, ask. When I met an E-6 from the Marines, I asked him what is his rank called & explain their enlisted ranks structure.

They were recruits. They are not Marines yet. They have not earned the privilege of calling enlisted personnel by their rank.

Don't ever call anyone in the Navy "Sir" unless they are an Officer. Had an airman keep calling me "Sir" - drove me up the wall. I kept correcting him, and I swear, he kept doing it just to irritate me. Anyway, if you see chevrons in the Navy it is "Petty Officer" - if you see a Gold Anchor, it is "Chief".

Here's what I found from my research and experience working in the joint world:
US Army
E-1 Address as “Private (last name)."
E-2 Address as “Private First Class (last name)."
E-3 Address as "Private (last name)."
E-4 Address as "Specialist (last name)."
E-5 thru E8 (non-First Sergeant) sergeants, staff sergeants, sergeants first class, and master sergeants: Address as "Sergeant (last name)."
E-8 First Sergeant (has diamond between upper and lower chevrons) Address first sergeants as "First Sergeant (last name)."
E-9 Address sergeants major as "Sergeant Major (last name)."

USMC
IAW GMK 1010…Speaking to enlisted Marines. Address them by rank and last name; avoid casual use of first name or nicknames. Senior enlisted Marines should also be addressed by their full rank and last name. Always refer to a Marine by rank, not pay grade.
E-1 Address as Private
E-2 Address as Private First Class
E-3 Address as Lance Corporal
E-4 Address as Corporal
E-5 Address as Sergeant
E-6 Address as Staff Sergeant
E-7 Address as Gunnery Sergeant
E-8 Address as Master Sergeant
E-8 Address as First Sergeant (has diamond between upper and lower chevrons)
E-9 Address as Master Gunnery Sergeant
E-9 Address as Sergeant Major (has star between upper and lower chevrons)

Navy
E-1 – E-3 Address as Seaman
E-4 Address as Petty Officer Third Class
E-5 Address as Petty Officer Second Class
E-6 Address as Petty Officer First Class
E-7 Address as Chief
E-8 Address as Senior Chief
E-9 Address as Master Chief

Air Force
E-1 – E-4 Address as Airman
E-5 thru E-8 Address as Sergeant
E-9 Address as “Chief”

Coast Guard
E-1 to E-3 Address as Seaman/Fireman/Airman and last name
E-4 to E-6 Address as Petty Officer and last name
E-7 Address as Chief
E-8 Address as Senior Chief
E-9 Address as Master Chief

Navy NCO's range from PO3 to MCPO, for PO3-1(E4-6) they are addressed as (rate abbreviation)3, 2, or 1. I am An Electronics Technician 2nd Class so ET2, below me would be ET3 and above would be ET1. Once a First Class Petty Officer makes Chief(E7) regardless of the rate they are referred to as Chief, E8 is Senior Chief, and E-9 is Master Chief. If you are going to shorten the addressing of any of the more senior pay grades it's Senior, and Master Chief (this one doesn't shorten)

How about "understood" responses for each branch?
Marine = Hoo-rah!
Army = Roger that!
Navy = Aye-aye!
Air Force = Cool!

In the Air Force it's Sgt until you see a Chief Master Sgt. You better address them as Chief. We only use full rank for formal occasions.

With respect even the wrong term won't cause an issue. Every branch is used to it. Just be respectful.