You're right to put nicht in front of a name like Maria, but this rule doesn't only apply to names. To explain this fully, let's break down nicht placement in general.
Usually, nicht will always go to the end of a sentence, unless it is negating a specific part of that sentence. When it is negating something specific, like a name, pronoun, adjective, or adverb, then it goes in front of the thing that it is negating.
Let's look at two examples:
1) Ich besuche dich heute nicht[, weil ich nach Berlin fahren muss]. "I won't visit you today [because I have to drive to Berlin]."
Here, nicht goes to the end of the clause because it is referring to the verb besuche, which is the core of the sentence. Essentially, it is negating the entire sentence.
2) Ich besuche dich nicht heute[, sondern vielleicht morgen]. "I won't visit you today[, but maybe (I will) tomorrow]."
Here, nicht is referring specifically to heute, so it comes in front of heute.
When you're talking about nouns, as in your example "That is not a soldier," nicht usually isn't used for negation. Instead, kein is used. (You can think of it as k + ein - it declines the same way as ein.) In situations where you feel you could maybe use both, kein is usually preferred over nicht. So your sentence would be Das ist kein Soldat, because we're talking about a noun. It doesn't have to be a living thing, either - we would also say Ich habe kein Geld "I don't have any money."
I hope that this quick breakdown was helpful! As with so many things in German, this will become more natural to you as you get more practice.