Some tricks I've seen:
Tricks with notable products
$(a + b)^2 = a^2 + 2ab + b^2$
This formula can be used to compute squares. Say that we want to compute $46^2$. We use $46^2 = (40+6)^2 = 40^2+2\cdot40\cdot6 +6^2 = 1600 + 480 + 36 = 2116$. You can also use this method for negative $b$:
$ 197^2 = (200 - 3)^2 = 200^2 - 2\cdot200\cdot3 + 3^2 = 40000 - 1200 + 9 = 38809 $
The last subtraction can be kind of tricky: remember to do it right to left, and take out the common multiples of 10:
$ 40000 - 1200 = 100(400-12) = 100(398-10) = 100(388) = 38800 $
The hardest thing here is to keep track of the amount of zeroes, this takes some practice!
Also note that if we're computing $(a+b)^2$ and a is a multiple of $10^k$ and $b$ is a single digit-number, we already know the last $k$ digits of the answer: they are $b^2$, then the rest (going to the right) are zeroes. We can use this even if a is only a multiple of 10: the last digit of $(10 * a + b)^2$ (where $a$ and $b$ consist of a single digit) is $b$. So we can write (or maybe only make a mental note that we have the final digit) that down and worry about the more significant digits.
Also useful for things like $46\cdot47 = 46^2 + 46 = 2116 + 46 = 2162$. When both numbers are even or both numbers are uneven, you might want to use:
$(a+b)(a-b) = a^2 - b^2$
Say, for example, we want to compute $23 \cdot 27$. We can write this as $(25 - 2)(25 + 2) = 25^2 - 2^2 = (20 + 5)^2 = 20^2 + 2\cdot20\cdot5 + 5^2 - 4 = 400 + 200 + 25 - 4 = 621$.
Divisibility checks
Already covered by Theodore Norvell. The basic idea is that if you represent numbers in a base $b$, you can easily tell if numbers are divisible by $b - 1$, $b + 1$ or prime factors of $b$, by some modular arithmetic.
Vedic math
A guy in my class gave a presentation on Vedic math. I don't really remember everything and there probably are a more cool things in the book, but I remember with algorithm for multiplication that you can use to multiplicate numbers in your head.

This picture shows a method called lattice or gelosia multiplication and is just a way of writing our good old-fashioned multiplication algorithm (the one we use on paper) in a nice way. Please notice that the picture and the Vedic algorithm are not tied: I added the picture because I think it helps you appreciate and understand the pattern that is used in the algorithm. The gelosia notation shows this in a much nicer way than the traditional notation.
The algorithm the guy explained is essentially the same algorithm as we would use on paper. However, it structures the arithmetic in such a way that we never have remember too many numbers at the same time.
Let's illustrate the method by multiplying $456$ with $128$, as in the picture. We work from left to right: we first compute the least significant digits and work our way up.
We start by multiplying the least significant digits:
$6 \cdot 8 = 48$: the least significant digit is $8$, remember the $4(0)$ for the next round (of course, I don't mean zero times four here but four, or forty, whatevery you prefer: be consistent though, if you include the zero here to make forty, you got do it everywhere).
$ 8 \cdot 5(0) = 40(0) $
$ 2(0) \cdot 6 = 12(0) $
$ 4(0) + 40(0) + 12(0) = 56(0) $: our next digit (to the left of the $8$) is $6$: remember the $5(00)$
$ 8 \cdot 4(00) = 32(00) $
$ 2(0) \cdot 5(0) = 10(00) $
$ 1(00) \cdot 6 = 6(00) $
$ 5(00) + 32(00) + 10(00) + 6(00) = 53(00) $: our next digit is a $3$, remember the $5(000)$
Pfff... starting with 2-digit numbers is a better idea, but I wanted to this longer one to make the structure of the algorithm clear. You can do this much faster if you have practiced, since you don't have to write it all down.
$ 2(0) \cdot 4(00) = 8(000) $
$ 1(00) \cdot 5(0) = 5(000)$
$ 5(000) + 8(000) + 5(000) = 18(000)$: next digit is an $8$, remember the $1(0000)$
$ 1(00) \cdot 4(00) = 4(0000) $
$ 1(0000) + 4(0000) = 5(0000) $: the most significant digit is a $5$.
So we have $58368$.
Quadratic equations
There are multiple ways to solve a quadratic equation in your head. The easiest are quadratic with integer coefficients. If we have $x^2 + ax + c = 0$, try to find $r_{1, 2}$ such that $r_1 + r_2 = -a$ and $r_1r_2 = c$. It is also possible to solve for non-integer solutions this way, but it is usually too hard to actually come up with solutions this way.
Another way is just to try divisors of the constant term. By the rational root theorem (google it, I can't link anymore sigh) all solutions to $x^n + ... + c = 0$ need to be divisors of $c$. If $c$ is a fraction $\frac{p}{q}$, the solutions need to be of the form $\frac{a}{b}$ where $a$ divides $p$ and $b$ divides $q$.
If this all fails, we can still put the abc-formula in a much easier form:
$ ux^2 + vx + w = 0 $
$ x^2 + \frac{v}{u}x + \frac{w}{u} = 0 $
$ x^2 + \frac{v}{u}x + \frac{w}{u} = 0 $
$ x^2 - ax - b = 0 $
$ x^2 = ax + b $ (This is the form that I found easiest to use!)
$ (x - \frac{a}{2})^2 = (\frac{a}{2})^2 + b $
$ x = \frac{a\pm\sqrt{a^2 + 4b}}{2} = \frac{a}{2} \pm \sqrt{(\frac{a}{2})^2 + b} $
I'm sure there are also a lot of techniques for estimating products and the like, but I'm not really familiar with them.
Tricks that aren't really usable but still pretty cool
See this excerpt from Feynman's "Surely you're joking, Mr. Feynman!" about how he managed to amaze some of his colleagues, and also this video from Numberphile.