How to Quickly Figure Out the Day of the Week Any Date Falls On
You know those people who somehow manage to pull the day of the week out of thin air, past or present, no matter how far off a date is? As it turns out, all it takes is a few simple mental tricks and you can wow the world with your uncanny ability to figure out any date's day of the week. 
You can go about this in a few different ways depending on your level of commitment. Below I'll highlight three methods, from easiest to most complicated. The first is also cheating: It involves using the internet rather than feats of mental acuity. The second and third methods both employ a little clever mental math.

The Extremely Easy Method: Ask Wolfram Alpha (or Siri)

Let's be honest: Most of the time, you've got a connection to the internet nearby. If you don't feel like learning and jumping through a few mental hula hoops, you can simply use a service like Wolfram Alpha to find out "what day of the week was July 4, 1776". It will tell you: Thursday. (This isn't a computation Google will one-box for you just yet, so good-on-you, Wolfram.)
What's kind of exciting for iPhone lovers is that Wolfram Alpha is baked into Siri, the automated voice assistant that ships with the iPhone 4S, so in theory you'll be able to simply ask Siri "what day of the week was July 4, 1776?" and it'll fetch the answer for you.

The Easy (but Short Term) Mental Trick: Prepare Your Mind a Few Months Forward and Backward

Reddit user GreggOttowa explains his method—good for a few months ahead or behind you:
For any given month, all the multiples of 7 fall on the same day. I usually have memorized what day that is for the current month and the next few months. So October is a "[F]riday month" and November is a "Monday month" and December is a "Wednesday month". You only have to memorize a new one every month.
Now when somebody says, "We should get together one Saturday. Say... December 12." you can snap back with "That's a Monday. Do you mean December 10?" All you have to do is find the nearest multiple of 7 and work from there. So when they ask about December 12, that's close to December 14 - which must be a Wednesday (since December 2011 is a Wednesday month).
The benefit of this method is that there's not a lot of mental overhead or memorization required. If you can remember that this November is a "Monday month" and December is a "Wednesday month", for example, you should be good at quickly snatching days of the week out of your brain for the rest of the year. Just remember that the 1st and 7th are not the same, so when you determine the base day for a month, you want to go by the 7th of the month or the last day of the previous month—the zero day—and not the 1st.
But let's say you want to be able to wow your friends and co-workers with more obscure dates (without turning to your phone). Things get a little more complicated.

The Hard (but More Robust) Way:

It's one thing to rattle of that the 20th of next November is a Sunday, but if I were to ask you to tell me the day of the week for July 4, 1776, things get a bit more complicated. For those calculations, we have to pull out bigger guns.
Web site Grey Matters has an extensive and detailed tutorial for determining the day of the week for any date thrown at you, no matter how far into the past or future, complete with plenty of mnemonics. The basic principles of this method look like this:
1) Day and Months Number Conversion: To work out the days of the week mentally, we need to convert them into numbers. We'll also need to convert the months into numbers, to adjust for their effects. These are taught in an easy-to-remember manner.
2) Addition of 3 Numbers: Without using a calculator, can you tell me what 6 + 6 + 31 is? That's about as difficult as the basic formula gets. If you're comfortable doing that, you won't have a problem working through the formula.
3) Subtracting Multiples of 7: Let's say you're asked about the 27th of a month. Regardless of the month or year, we can state with certainty that the 27th of a month will fall on [the same day of the week as] the 6th (since it's 3 weeks, or 21 days, earlier). Since adding 6 is simpler than adding 27, and will give the same result, why not use 6? If you learn to subtract multiples of 7, this makes the arithmetic so easy that you won't have to worry about addition problems any tougher than 6 + 6 + 6!
4) Year Number Conversion: After becoming comfortable with all of the above when given dates in the years 2000 to 2003, you'll learn how to remember and adjust the leap years in the 21st century to key dates. After learning those, you'll learn a simple way to adjust for any year from 2000 to 2099, and even adjust for other centuries!
If that sounds a little too complicated, you may prefer to stick with one of the decidedly simpler methods above. The Grey Matters guide is well written, detailed, and full of helpful mnemonics, though, and if you're really interested in training your brain to incorporate a new skill (of dubious usefulness), it'll get you there.