First, consider the question without a negative:
Did you go to the store?
This question is asking if you did go to the store. Therefore, 'yes' and 'no' are respectively answers of
[Yes,] I did go to the store
[No,] I didn't go to the store.
You answer 'yes' to indicate that the statement "you did go to the store" is true; 'no' indicates that this statement is false.
The question you wish to answer asks for the negation of this statement
Since the question is now
Did you not go to the store?
you are now answering for the statement "you did not go to the store."
If this statement is true, then you answer yes.
However, as other answers have pointed out, a question phrased this way often displays or conveys a certain expectation, and sometimes isn't even meant as a question. This may be where the uncertainty in how to answer comes from.
Therefore, a full answer that addresses any ambiguity caused by expectations or implications would be
Yes, I did not go to the store.
or the negation,
No, I did go to the store.
(which you might consider as "I didn't not go to the store," which can be difficult to understand for some.)
If you were then to answer the question with solely 'yes' or 'no', you would say 'yes' if you did, in fact, go to the store.
For those unconvinced, consider how one would go about asking for the negation of a question if not in precisely this way - and if the trouble would be worth that interpretation.