Why should/does(?) statistical sampling work for politics (e.g. Gallup)? Polls out there (say, Gallup) sample some absurdly low number of people compared to the population size (e.g. maybe a thousand people out of hundreds of millions).  
Now, to me, sampling a population as a means for estimating the population's statistics makes sense when you have a strong reason to believe the samples are representative of the population (or, similarly, of other samples).  
For example, sampling obviously makes sense for medical studies, because we know a priori that humans all have quite similar genomes and that this factor makes their bodies behave similarly.
Note that this isn't some kind of loose coupling -- genome is a pretty damn strong determining factor.
However, I just don't understand what justifies using low sample sizes for things like political polls.  
I could buy that maybe 80-90% of the people in any given neighborhood vote similarly for the president (due to similar socioeconomic/education backgrounds), but this hardly seems to justify the absurdly low number of samples. There is literally no compelling reason (at least to me) why 1000 random voters should behave like the 200 million other voters.  
To me, you'd need at least like (say) 100× that amount. Why? I can think of a bunch of reasons, e.g.:


*

*There are ~22,000 precincts just in California. People grow up so differently in their economic and educational backgrounds that a poll of size 1000 seems laughably small. How can you summarize entire precincts with < 1 person on average?

*People can't generally change their bodies' responses to medicine, but they can change their opinions about politics just by thinking about it. The way I see it, there's no forcing factor akin to DNA in medicine when you're dealing with politics. At best I'd imagine there should be small pockets of correlation.
Yet somehow, polls like this seem to... work anyway? Or at least people seem to think they do?
But why should they? Maybe I just fundamentally don't understand sampling? Can someone explain?
I just can't take any of the polls I see seriously, but I feel like I'm in more or less alone in this...
 A: Firstly, this is aside from your main points but it's worth mentioning. In the medical trial you could have 1000 people testing a drug which can be given to the 10000 people who are sick annually. You might look at that and think "That's being tested on 10% of the population", in fact the population isn't 10000 people, its all future patients so the population size is infinite. 1000 people isn't large compared to the infinite potential users of the drug but these kinds of studies work. It's not important whether you test 10%, 1% or 0.1% of the population; what's important is the absolute size of the sample not how big it is compared to the population.
Next, your main point is that there are so many confounding variables which can influence people's voting. You're treating the 22000 districts of California like 22000 variables but really they are just a handful of variables (income and education like you mentioned). You don't need a representative sample from every district, you just need enough samples to cover the variation due to income, education, ect.
If you have $k$ confounding variables (age, gender, education, ect) and they all have similar effects then the variance of the vote increases by about $k$ times. If you sample $n$ people then the variance of the sample average decreases by a factor of $n$. Therefore, if the variation from each confounding variable is $\sigma^2$ then your sample average from $n$ people with $k$ confounding variables will be $\frac{k\sigma^2}{n}$. 
You can probably think of 10 or so confounding variables but the sample size is 1000 so $k$ is a lot smaller than $n$. Therefore the variance of the sample average is quite small. 
Edit: 
The above formula was assuming that each confounding variable is equally important. If we want to consider hundreds of things that can add variance to the results then this assumption isn't valid (e.g. maybe twitter users support one candidate more, but we know that twitter use isn't as important as gender).
We could list all the confounding variables in order of importance (e.g. gender, age, income, ... , twitter use, ...). Let's assume that each variable is only 90% as important as the previous one. Now if gender adds a variance equal to $\sigma^2$ then age adds a variance equal to $0.9 \sigma^2$ and income adds $0.9^2 \sigma^2 $. If we include an infinite number of confounding variables then the total variability is $\sum_{n=0}^{\infty} \sigma^2 0.9^n = 10 \sigma^2$.
With this type of consideration for minor variables we've ended up with a variance with 10 times the variability of gender alone. So with $n$ samples the variation in the sample average is $\frac{10\sigma^2}{n}$. Of course $0.9$ was chosen arbitrarily but this conveys a point about how these infinite number of minor variables should add up to something small
A: It seems like you're imagining a very simple sampling model.
The simplest model for sampling is called aptly Simple Random Sampling. You select a subset of the population (e.g., by dialing phone numbers at random) and ask whomever answers how they're voting. If 487 say Clinton, 463 say Trump, and the remainder give you some wacky answer, then the polling firm would report that 49% of voters prefer Clinton, while 46% prefer Trump. However, the polling firms do a lot more than this. A simple random sample gives equal weight to every data point. However, suppose your sample contains--by chance--600 men and 400 women, which clearly isn't representative of the population as a whole. If men as a group lean one way, while women lean the other, this will bias your result. However, since we have pretty good demographic statistics, you can weight* the responses by counting the women's responses a bit more and the men's a bit less, so that the weighted response represents the population better. Polling organizations have more complicated weighing models that can make a non-representative sample resemble a more representative one. 
The idea of weighting the sampled responses is on pretty firm statistical ground, but there is some flexibility in choosing what factors contribute to the weights. Most pollsters do reweight based on demographic factors like gender, age, and race. Given this, you might think that party identification (Democratic, Republican, etc) should also be included, but it turns out that most polling firms do not use it in their weights: party (self)-identification is tangled up with the voter's choice in a way that makes it less useful. 
Many polling outfits also report their results among "likely voters". In these, respondents are either selected or weighted based on the likelihood that they'll actually turn up to the polls. This model is undoubtedly data-driven too, but the precise choice of factors allows for some flexibility. For example, including interactions between the candidate and voter's race (or gender) wasn't even sensible until 2008 or 2016, but I suspect they have some predictive power now.
In theory, you could include all sorts of things as weighting factors: musical preference, eye color, etc. However, demographic factors are popular choices for weighting factors because:


*

*Empirically, they correlate well with voter behavior. Obviously, there is no iron-clad law that 'forces' white men to be lean Republican, but over the last fifty years, they have tended to. 


*

*The population values are well known (e.g., from the census or Vital Records)



However, pollsters also see the same news everyone else does, and can adjust the weighting variables if necessary.
There are also some "fudge factors" that are sometimes invoked to explain poll results. For example, respondents sometimes are reluctant to give "socially-undesirable" answers. The Bradley Effect posits that white voters sometimes downplay their support for white candidates running against a minority to avoid appearing racist. It is named after Tom Bradley, an African-American gubernatorial candidate who narrowly lost the election despite leading comfortably in the polls. 
Finally, you're completely correct that the very act of asking someone's opinion can change it. Polling firms try to write their questions in a neutral way. To avoid issues with the order of possible responses, the candidates' names might be listed in random order. Multiple versions of a question are also sometimes tested against each other. This effect can also be exploited for nefarious ends in a push poll, where the interviewer isn't actually interested in collecting responses but in influencing them. For example, a push poll might ask "Would you vote for [Candidate A] even if it was reported that he was a child molester?". 

* You might also set explicit targets for your sample, like including 500 men and 500 women. This is called stratified sampling--the population is stratified into different groups, and each group is then sampled random. In practice, this isn't done very often for polls, because you'd need to stratify into a lot of exhaustive groups (e.g., college-educated men between 18-24 in Urban Texas). 
A: There's a mathematical theorem called the "law of large numbers." Imagine that you want to determine the probability that a coin will come up heads. The "population" of coin flips is infinity - much larger than the 300,000,000+ people in the United States. But according to the Law of Large Numbers, the more coin flips you do, the more accurate your estimate will be. 
The ideal poll: In the ideal poll, the pollsters would randomly choose names from the U.S. Census, they would find out where those people live, then they would go and knock on their door. If the person says they're planning on voting, the pollster asks who they're voting for and records their answer. Polling like this is mathematically guaranteed to work and the amount of error in your measurement for any given confidence level can be calculated easily. 
Here's what the error means: Suppose that based on your poll, you got that there's a 52 percent chance Candidate Awesome McPerfect is going to win, with a 3% error with 98% confidence. That means that you can be 98% confident that the true portion of voters who favor candidate Awesome McPerfect is between 49% and 55%.
A Note on Error and Confidence For a given sample size, the more confident you are, the bigger your error will be. Think about it - you're 100% confident that the true proportion that support canditate Awesome is between 0% and 100% (most error possible), and you're 0% confident that the true proportion that supports canditate Awesome is exactly 52.0932840985028390984308% (zero error). More confidence means more error, less confidence means less error. However, the relationship between confidence and error is NOT linear! (See: https://en.wikipedia.org/wiki/Confidence_interval)
Polls in the real world: Because it's expensive to helicopter pollsters out to all parts of the country to knock on the doors of random people (although I'd love to see that happen; if you're a billionare and you see this, please consider funding this), polls in the real world are more complex. Lets look at one of the more common strategies - calling up random voters and asking them who they'd vote for. It's a good strategy, but it does have some well-aknowledged failings:


*

*People often choose not to answer the phone and respond to pollsters (ex. me)

*Some demographics are more likely to have a landline (ex. older voters)

*Some demographics are more likely to respond to pollsters (ex. older voters)


Because different demographics vote in different ways, pollsters have to do their best to control for the differences in their raw data (based on who decided to answer the phone) and the outcomes of actual elections. For example, if 10% of people who picked up the phone were hispanic, but 30% of voters in the last election were hispanic, then they're going to give three times the weight to hispanic voters in their poll. If 50% of people who answered the phone were older than 60, but only 30% of the people who voted in the last election were older than 60, they're going to give less weight to the older voters who responded. It's not perfect, but it can lead to some impressive feats of prediction (Nate Silver correctly predicted the results in each of the 50 states in the 2012 election using statistics, and he was correct in 49 out of the 50 states in the 2008 prediction). 
A word of caution to the wise: Pollsters make the best predictions they can based on how things worked out in the past. Generally speaking, things work out about the same now as they did in the past, or at least the change is slow enough that the recent past (which they focus most on) will resemble the present. However, occasionally there are rapid shifts in the electorate and things go wrong. Maybe Trump voters are slightly less likely than your average voter to answer the phone, and weighting by demographics doesn't account for that. Or Maybe young people (who overwhelmingly support Hillary) are even more unlikely to answer the phone than the models predict, and the ones that do answer the phone are more likely to be republican. Or perhaps the opposite of both is true - we don't know. things like that are hidden variables that don't show up in commonly collected demographics. 
We would know if we sent pollsters to knock on random doors (ahem, imaginary billionare reading this), since then we wouldn't have to weight things based on demographics, but until then, fingers crossed. 
A: Perhaps someone can post a more enlightening answer as to why, but judging from the last two US elections, I'm forced to conclude exactly what I had suspected prior to the 2016 elections:
It appears our polling methodologies in fact do not work for elections.
There isn't yet a consensus on why this appears to be the case, but some hypotheses I've found have been the following:

*

*Supporters of some candidates may be more likely to respond due to enthusiasm. [1, 2]

*Supporters of some candidates may be less likely to respond due to distrust. [1, 2, 4]

*We poll too often and compromise on sample size/quality, mistaking noise for signal. [1, 2]

*Weightings that we do to correct for demographics biases may be inadequate. [3]

Links with more discussions on the topic:

*

*(NYMag) Should We Stop Paying Attention to Election Polls?


*(NYT) Why Did the Pre-Election Polls Get It So Wrong Again?


*(538) Trump Supporters Aren’t ‘Shy,’ But Polls Could Still Be Missing Some Of Them


*(Vox) Election results: Why the polls got it wrong
