Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.
I tried to look it up at a few places (including Sipser) but I could not make out a lot of sense from the proofs. I would appreciate it if someone can give me a proof (or clear intuition) on this.
Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$
It turns out that this number is well defined (called Ramsey number) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$
A well known upper bound for Ramsey number states $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \; (1)$$ if $s = t$ then the above reduces to the central binomial coefficient ${2t-2 \choose t-1}$ which is always smaller than $2^{2t}$
To prove $(1)$ one can use induction on $s+t$. Leaving the induction base $R(1,t), R(s,1)$ as an exercise for you let us suppose the inequality holds for all $s+t < k$ and let $G$ be a graph with $R(s,t-1)+R(s-1,t)$ vertices.
Let $v$ be an arbitrary vertex of $G$ and partition the remaining vertices of the graph into two groups $A,N$ - those adjacent with $v$ and those that are not adjacent with $v.$ Now since $$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ we have either $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ Now if the first inequality is satisfied then the graph induced by $N$ either contains a $s$-clique or the graph induced by $N \cup \{v\}$ contains an independent set of size $t.$ In particular this implies that in this case $G$ either contains a $s$-clique or independent set of size $t.$ The second case is verified analogously and establishes the first part of the stated bound. For the last part observe that $${s+t-3 \choose s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$
