The DM should convey "the naga is casting a spell"

Counterspell has a casting time of 1 Reaction...

which you take when you see a creature within 60 feet of you casting a spell

Counterspell says "casting" not "casts", indicating that once the spell is actually cast, it is too late to counter. Your impression of the order of operations is correct:

1. Casting (for 1 Action spells this involves several seconds of chanting, arm-waving, etc.)
2. (Optional) counterspell
3. Cast
4. Saving throws, attack rolls, etc.
5. Effects

In order for you the player to know when your character can use counterspell, the DM will need to indicate that spellcasting is occurring. However, the DM is (probably) human, so they can make mistakes.

From the beginning of "Playing the Game" in the Basic Rules, the game follows the following steps:

1. The DM describes the environment.
2. The players describe what they want to do.
3. The DM narrates the results of their actions.

Spellcasting typically involves verbal, somatic, and/or material components, the first two of which are quite obvious and should be described. The spell dominate person requires verbal and somatic components. (Though a spirit naga only needs the verbal components.)

• Verbal components involve the "chanting of mystic words ... with specific pitch and resonance".
• Somatic components involve "forceful gesticulation or an intricate set of gestures".
• Material components involve "particular objects", but may be replaced by a spellcasting focus (so they may or may not be obvious).

This may seem like unnecessary fluff, but counterspell relies on you seeing those components being performed.

From one of your comments, it sounds like the DM had the naga roll Stealth to avoid counterspell. There are no explicit mechanics for using Stealth to conceal spellcasting, and there are a couple of problems with allowing it:

1. Every spell will start with a Stealth roll. If it's free, why not do it every time?
2. Verbal components are "chanting of mystic words ... with specific pitch and resonance". I take this to mean that spellcasting is largely at a fixed volume.
3. It gives every spellcaster the Subtle Spell metamagic from sorcerer - without the resource cost.
4. It increases the value of the already-powerful Perception and Stealth skills for spellcasters. If you knew about these houserules at character creation, you may have made different choices. The Observant and Prodigy feats are more desirable, for starters.

Due to the DM not describing the environment (that is, the components) accurately, you and your DM have different perspectives on what occurred.

From your perspective

DM: Make a Wisdom save.

You: Must be some kind of ability the naga has, since spellcasting would be obvious. Can't counter non-spells. (You roll the save.) I got a 12.

DM: You're now mind controlled.

You: That's no good. I'd better double-check that it wasn't a spell. That wasn't a spell, right?

DM: It was a spell.

You: Then I would have used counterspell.

DM: It's too late!

You: This is like falling in a hole that the DM forgot to describe. That's not fair!

From the DM's perspective

DM: This naga is going to use dominate person on that character. I'll make a Stealth check to hide the spellcasting. That beats the wizard's passive Perception. Make a Wisdom save.

You: (You roll the save.) I got a 12.

DM: You're now mind controlled. The player didn't yell "counterspell" here, so they missed their chance.

You: That wasn't a spell, right?

DM: It was a spell.

You: Then I would have used counterspell.

DM: This player is trying to take advantage of the situation. They want to conserve their counters by waiting until they see the result. It's too late!

You: That's not fair!

Resolving the situation

Your goal should be resolving those differences in perspective.

You need to talk with your DM outside of a session (just before or after one works). Present your perspective and ask how the DM wants to handle counterspell in the future. Include the fact that many monsters have non-spell abilities that force a saving throw, and that counterspell is triggered when you see a creature casting a spell. Your DM may not understand the issues with easily-concealed spellcasting.

If your DM wants to keep Stealth spellcasting, be sure you know how this houserule works. In order to follow the rules reasonably well, though, I would recommend one of the following two paths:

1. Announce the name of all spells as they are being cast. The (N)PCs shouldn't technically know that dominate person is being cast (without a check), but this speeds everything up. If the (N)PC wants to counterspell, they declare it then, before everyone rolls saves.
2. Announce that (unnamed) spellcasting is occurring, then pause. If the (N)PC wants to counterspell, they do so before the name, saves, or effects of the spell are described.

I prefer the second choice, as it's not much slower than the first, and it encourages tactical play. I recommend that you use the same method for both PCs and NPCs: either you both counterspell knowing the spell, or you both counterspell blind.

As Mark Wells points out in the comments, this may have been avoided by asking "is the naga casting a spell" as soon as possible (barring any Stealth shenanigans). I frequently play AL games with various DMs, so I have adopted a more proactive approach to using abilities. If you explain why you're asking, most DMs will have no problem explaining the situation.