There are two notions of "mod", but I'm afraid that your description is incorrect for both.
What you describe, "how many times a number goes into another number while leaving a remainder" is the following: If you are dividing $b$ by $a$, and you write $b = qa + r$ with $0\leq r \lt |a|$, then $r$ is called the "remainder", and $q$ is called the quotient. What you describe is $q$, the quotient.
Now, to the two notions of "modulo":
Modulo operation
This is very common in Computer Science. Here, $\bmod$ is a binary operation (like $+$, $-$, $\times$).
The precise definition varies from language to language. A common one is the following:
if $a$ and $b$ are integers, and $a\neq 0$, then
$b\bmod a$ (pronounced exactly like it's written) is defined to be the remainder when dividing $b$ by $a$. That is, if we write $b=qa + r$ with $0\leq r\lt|a|$, then $b\bmod a$ is defined to be $r$. Therefore, $7\bmod 3 = 1$ (because $7=2\times 3 + 1$), $43\bmod 13 = 4$ (because $42 = 3\times 13 + 4$), and $1001\bmod 13 = 0$ (because $1001 = 77\times 13 + 0$). This "mod" does indeed only give you nonnegative numbers.
There are other versions of the modulo operator; some, return the "residue class of smallest absolute value" (for example, modulo $3$ will return either $-1$, $0$, or $1$, rather than $0$, $1$, or $2$; and modulo $7$ will return $-3$, $-2$, $-1$, $0$, $1$, $2$, or $3$). Others, as robjohn mentions in comments, return a remainder of the same sign as $a$, others of the same sign as $b$.
Modulo relation
This is more common in mathematics. Given an integer $n$, we define a relation called "congruent modulo $n$" as follows: we say that two integers $a$ and $b$ are "congruent modulo $n$", written $a\equiv b \pmod{n}$, if and only if $b-a$ is a multiple of $n$. Note that $a$, $b$, and $n$ can be positive, negative, or zero.
This is what you are seeing: $-8\equiv 7\pmod{5}$ is true, because $7-(-8)=15$ is a multiple of $5$. $2\equiv -3\pmod{5}$ because $-3-2 = -5$ is a multiple of $5$. $-3\equiv -8\pmod{5}$ because $-8-(-3) = -5$ is a multiple of $5$.
Note that this is a relation: you don't get a number "out of it", like you do with the modulo operation above; this is a statement about whether two numbers are related.
Connection between the two notions
The simplest connection between the two concepts is the following:
Theorem. Let $a$ and $b$ be integers, and let $n\neq 0$ be a nonzero integer. Then
$$a\equiv b\pmod{n}\textit{ if and only if } a\bmod n = b\bmod n.$$
That is: $a$ and $b$ are congruent modulo $n$ if and only if they leave the same remainder when divided by $n$.
Proof. Suppose that $a\equiv b\pmod{n}$, and write $a=qn + r$, $b=pn+s$, with $0\leq r\lt |n|$, $0\leq s\lt |n|$. Then $a\equiv b\pmod{n}$ if and only if $(qn+r)-(pn+s) = (q-p)n + (r-s)$ is a multiple of $n$; this occurs if and only if $r-s$ is a multiple of $n$, which occurs if and only if $|r-s|$ is a multiple of $n$.
But $0\leq |r-s|\lt|n|$; the only multiple of $n$ that has absolute value smaller than $|n|$ is $0$. So $r-s$ is a multiple of $n$ if and only if $|r-s|=0$, if and only if $r=s$. Since $r=a\bmod n$ and $s=b\bmod n$, we conclude that $a\equiv b\pmod{n}$ if and only if $a\bmod n = b\bmod n$. $\Box$
Best Answer
That is the set of integers mod $p$. Mod $p$ does, like you said, deal with remainders of integers when divided by $p$. But the only possible remainders when dividing by $p$ are $0, 1, ..., p-1$. Thus the set of integers "mod $p$" is the set of these possible remainders.