Matrices commute if and only if they share a common basis of eigenvectors?

Suppose that $A$ and $B$ are $n\times n$ matrices, with complex entries say, that commute.
Then we decompose $\mathbb C^n$ as a direct sum of eigenspaces of $A$, say $\mathbb C^n = E_{\lambda_1} \oplus \cdots \oplus E_{\lambda_m}$, where $\lambda_1,\ldots, \lambda_m$ are the eigenvalues of $A$, and $E_{\lambda_i}$ is the eigenspace for $\lambda_i$. (Here $m \leq n$, but some eigenspaces could be of dimension bigger than one, so we need not have $m = n$.)

Now one sees that since $B$ commutes with $A$, $B$ preserves each of the $E_{\lambda_i}$: If $A v = \lambda_i v, $ then $A (B v) = (AB)v = (BA)v = B(Av) = B(\lambda_i v) = \lambda_i Bv.$

Now we consider $B$ restricted to each $E_{\lambda_i}$ separately, and decompose each $E_{\lambda_i}$ into a sum of eigenspaces for $B$. Putting all these decompositions together, we get a decomposition of $\mathbb C^n$ into a direct sum of spaces, each of which is a simultaneous eigenspace for $A$ and $B$.

NB: I am cheating here, in that $A$ and $B$ may not be diagonalizable (and then the statement of your question is not literally true), but in this case, if you replace "eigenspace" by "generalized eigenspace", the above argument goes through just as well.

This is false in a sort of trivial way. The identity matrix $I$ commutes with every matrix and has eigenvector set all of the underlying vector space $V$, but no non-central matrix has this property.

What is true is that two matrices which commute and are also diagonalizable are simultaneously diagonalizable. The proof is particularly simple if at least one of the two matrices has distinct eigenvalues.

Let $S$ be a set of commuting matrices over an algebraically closed field $F$. Then there may not be a common basis of eigenvectors (since any of them may not be diagonalizable!) but there must be at least a common eigenvector:

Burnside's theorem on matrix algebras states that if $F$ is algebraically closed, $V$ is a finite-dimensional $F$-vector space and $S$ is a proper subalgebra of $\text{End}(V)$ then there exists a nontrivial $S$-invariant subspace, i.e, there exists $W\leq V$ with $0\neq W\neq V$ such that $s(W)\subseteq W$ for every $s\in S$.

Suppose $S\subseteq M_n(F)$ with $n>1$ is commuting. Observe that a subspace of $F^n$ is $S$-invariant if and only if it is invariant for $<S>$, the subalgebra of $M_n(F)$ generated by $S$. Since $S$ is commuting, $<S>$ is also commuting and therefore $<S>\neq M_n(F)$. Burnside's theorem applies, and so there exists a proper and nontrivial subspace $V\leq F^n$ which is invariant for all $S$. If $V$ has dimension more than $1$ then $<S>\neq\text{End}(V)$, since $<S>$ is commuting, and we can apply Burnside's theorem again. By induction there exists an $S$-invariant subspace of dimension $1$, and so a common eigenvector for the matrices in $S$.

An elementary argument.

Summary: show that each eigenspace of $A$ has a basis such that each basis vector is contained in one of the eigenspace of $B$. This basis is then the simultaneous common basis we are looking for.

Suppose $A,B$ are both diagonalizable and they commute.

Now let $E_{\lambda_i}$ be eigenspaces of $A$ for each distinct eigenvalue $\lambda_i$ of $A$.

Now let $F_{s_i}$ be eigenspaces of $B$ for each distinct eigenvalue $s_i$ of $B$.

Now I claim that $E_{\lambda_i}$ (of say dimension $m$) has a basis $v_1^i,...,v_m^i\in E_{\lambda_i}$ such that each $v_r^i$ is in one of $B$'s engenspace $F_{s_j}$--this would imply these $v_r^i$ are eigenvectors of $B$ and $A$ simultaneously. Apply this to all eigenspaces $E_{\lambda_i}, i=1,...,n$. The collection of all $v_r^i$ then becomes a common basis for $A$ and $B$ as required.

To show this claim, first pick arbitrary basis $w_1,...,w_m$ of $E_{\lambda_i}$. Each $w_i$ can be written as sum of vectors where each vector is in one of $B$'s engenspace $F_{s_j}$. This is a subtle point so let me repeat: for each $i=1,...,m,$ $w_i=z_1^i+...+z_{l_i}^i, l_i\le m$ and $z_k^i\in F_{s_j}$ for some $j$. This is trivially true because direct sum of $B$'s engenspaces is the entire space.

Now we make a second claim that all $z_k^i\in E_{\lambda_i}$. Then the collection of all $z_k^i$ span $E_{\lambda_i}$ and thus the collection can be reduced to a basis $v_1,...,v_m$ where each $v_j$ is contained in $E_{\lambda_i}$ as required by the first claim.

Note that $B$ is invariant to $E_{\lambda_i}$ since $A,B$ commute. The second claim follows from: $\sum_{i=1}^N z_i \in S$ where $z_i$ are eigenvectors of distinct eigenvalues of $B$ and $S$ is a subspace to which $B$ is invariant, then $z_i\in S,\forall i$. We check this by induction on $N$. It is trivially true for $N=1$. Then suppose $Bz_1=\lambda z_1$. Since $\lambda(z_1+...+z_N)\in S$ and $B(z_1+...+z_N)\in S$, we have $B(z_1+...+z_N)-\lambda(z_1+...+z_N)=a_2z_2+...+a_Nz_N\in S$ for some constant $a_i\neq 0$--the constants are non-zero because we assumed $z_i$ all have distinct eigenvalues. Then apply inductive hypothesis $z_2,...,z_N\in S$. This would imply $z_1\in S$ as well. This finishes the proof.