First, in your use of printf you are telling it to print the number as signed ("%d") instead of unsigned ("%u").
Second, you are right in that it has "something to do with the way numbers are stored in memory". An int (signed or unsigned) is not a single bit on your computer, but a collection of k bits. The exact value of k depends on the specifics of your computer architecture, but most likely you have k=32.
For the sake of succinctness, lets assume your ints are 8 bits long, so k=8 (this is most certainly not the case, unless you are working on a very limited embedded system,). In that case (int)0 is actually 00000000, and (int)~0 (which negates all the bits) is 11111111.
Finally, in two's complement (which is the most common binary representation of signed numbers), 11111111 is actually -1. See http://en.wikipedia.org/wiki/Two's_complement for a description of two's complement.
If you changed your print to use "%u", then it will print a positive integer that represents (2^k-1) where k is the number of bits in an integer (so probably it will print 4294967295).