This is one thing that keeps bugging me, and maybe there's a direct answer.
Grammatically, which one is more correct of these two? Does it make a difference?
I tried not to do that.
I tried to not do that.
As some others have said, both are correct, and it is not wrong to say
However, that is not the full story. Searching the Corpus of Contemporary American for various phrases (not to hold vs to not hold; not to know vs to not know; not to go vs to not go) reveals that the not to <verb> form is far more common:
(Note that I didn't search for "not to [any verb]", because that also picks up certain fixed expressions such as "not to mention ..." which might distort the picture.)
So it's clear that the not to <verb> form is far more common. Furthermore, looking at the context of a sample of the to not <verb> examples, most of them appeared to be in speech (either on the radio, or quoted in a magazine), or very informal writing.
Searching the British National Corpus gives an even clearer bias - there, not to <verb> dominates by about 99%.
So in general usage, it is clear that not to <verb> is preferred by most writers.
Why is this? And when should one choose one expression or the other? Naturally this is rather subjective, so take the following explanation as my personal view on the matter, but note that it is consistent with what a lot of other people think.
So when might one want to say to not <verb>?
The normal form of a negative infinitive is "not to X", in all contexts.
The form "to not X" is grammatical (notwithstanding the generations of people who have moaned about "splitting the infinitive"), but unusual, and would only be used in order to convey a special meaning.
So "I try not to care" would be normal, but "I try to not care" would be spoken with an emphasis on the "not", and would suggest that I am trying very hard to do something specific "not caring" instead of caring.
Some people will tell you that you should say "I tried not to do that."
However, this is what I think:
When you say, "My goal was to do X," it's clear what that you had a goal and that it was to do X. When you say, "My goal was not to do X," was you goal to ensure that you not do X ("I tried not to do X"), or was doing X just not a goal ("My goal was not to do X but to do Y")? In context it might be clear what you mean based on whether or not you have the "but to do Y" part.
In the example you gave, someone saying that doing "that" simply wasn't a goal of theirs might say "I did not try to do that."
Even if ambiguity does arise, my statement is that you can go right ahead and say "I tried to not do that" if you and your audience are fine with it (or maybe even if your audience isn't fine with it but you choose to ;). In fact, I might recommend it.
Unless split infinitive is specifically warranted, we ought to go with the natural flow of NOT+TO+VERB.