While most of existing answers pointed out the multicollinearity is one common cause of this paradox, it seems that none of them demonstrated why it is so from the mathematical perspective. This answer tries to fill this gap.
To make notations less cluttered, suppose the number of regressors is $2$ and the number of observations is $n$, so the model can be written as:
\begin{align}
y_i = \beta_0 + \beta_1X_{1, i} + \beta_2X_{2, i} + \epsilon_i, \quad
i = 1, 2, \ldots, n.
\end{align}
We are interested in testing
A single $\beta_i$ is $0$:
\begin{align}
& H_0: \beta_1 = 0 \text{ v.s. } H_1: \beta_1 \neq 0. \tag{1.1}\label{1.1} \\
& H_0: \beta_2 = 0 \text{ v.s. } H_1: \beta_2 \neq 0. \tag{1.2}\label{1.2}
\end{align}
All $\beta$s are 0:
\begin{align}
H_0: \beta_1 = \beta_2 = 0 \text{ v.s. } H_1: \beta_1 \neq 0 \text{ or }
\beta_2 \neq 0. \tag{2}\label{2}
\end{align}
It is well-known that the testing procedures applying to problem $\eqref{1.1}$-$\eqref{1.2}$ and $\eqref{2}$ are $t$-test and $F$-test respectively. However, the key to explain the posed paradox is recognizing the $t$-test to problem $\eqref{1.1}$-$\eqref{1.2}$ can also be viewed as an equivalent $F$-test, so that we are actually applying the partial $F$-test to problem $\eqref{1.1}$-$\eqref{1.2}$ and the overall $F$-test to problem $\eqref{2}$ respectively (a good reference to this is Applied Linear Statistical Models by Kutner et al., Section 7.3), whose testing statistics are
\begin{align}
F_1 = \frac{MSR(X_1|X_2)}{MSE} = \frac{SSR(X_1|X_2)}{MSE} = \frac{SSR(X_1, X_2) - SSR(X_2)}{MSE} \tag{3.1}\label{3.1} \\
F_2 = \frac{MSR(X_2|X_1)}{MSE} = \frac{SSR(X_2|X_1)}{MSE} = \frac{SSR(X_1, X_2) - SSR(X_1)}{MSE} \tag{3.2}\label{3.2}
\end{align}
and
\begin{align}
F_0 = \frac{MSR(X_1, X_2)}{MSE} = \frac{SSR(X_1, X_2)}{2MSE} \tag{4}\label{4}
\end{align}
respectively. At the significance level $\alpha$, $F_1$ and $F_2$ are compared with $q_1^* = F_{1, n - 3}(1 - \alpha)$, while $F_0$ is compared with $q_2^*= F_{2, n - 3}(1 - \alpha)$, to determine whether $H_0$ should be rejected.
The key concept in the test statistic $\eqref{3.1}$ is the term $SSR(X_1|X_2)$, known as sequential/extra sums of squares (see Chapter 7 of the same reference above and this link for more details), which accounts for the reduction in the error sum of squares caused by adding $X_1$ to the regression model when $X_2$ is already in the model. Thus $SSR(X_1|X_2)$ measures the marginal effect of adding $X_1$ to the regression model when $X_2$ is already in the model. Clearly, $SSR(X_2|X_1)$ bears the same interpretation. Having understood this concept, comparing $\eqref{3.1}$-$\eqref{3.2}$ against $\eqref{4}$ immediately indicates a scenario such that the overall $F$-test is significant while partial $F$-tests are insignificant, namely when $SSR(X_1, X_2)$ is big but both $SSR(X_1|X_2)$ and $SSR(X_2|X_1)$ are small (relative to $MSE$). In other words, the variation of $y$ can be adequately explained by any simple regression model where the single predictor is $X_1$ or $X_2$ (therefore $SSR(X_i)$ is big, and as a result $SSR(X_1, X_2)$ is big), but when we tried to further increase the $y$-variation explain ratio by adding the remaining variable to the existing simple regression model, the improvement is very limited (therefore both $SSR(X_1|X_2)$ and $SSR(X_2|X_1)$ are small). One example that fits this setting is multicollinearity, as described in @Rob Hyndman's answer. However, multicollinearity is not the only example that fits the general setting, as I will briefly discuss at the end of this answer.
Now let's deepen the above observation with the help of linear algebra -- my goal is to re-express $\eqref{3.1}$ and $\eqref{3.2}$ in such a manner that all sums of squares can be interpreted as vector lengths. To this end, let $y = (y_1, \ldots, y_n)' \in \mathbb{R}^n$, $e = (1, \ldots, 1)' \in \mathbb{R}^n$, $x_i = (X_{i, 1}, \ldots, X_{i, n})' \in \mathbb{R}^n, i = 1, 2$, $X = \begin{bmatrix} e & x_2 & x_1\end{bmatrix}$ (note that $x_2$ precedes $x_1$ because we let $x_2$ enter the model first). Furthermore, let $X = QR$ be the QR decomposition of $X$, where $Q = \begin{bmatrix} q_1 & q_2 & q_3\end{bmatrix}$. Following the calculation in this answer, it can be shown that
\begin{align}
& SSR(X_1, X_2) = y'(q_2q_2' + q_3q_3')y = \|P_{[q_2, q_3]}y\|^2, \tag{5}\label{5} \\
& SSR(X_1|X_2) = y'q_3q_3'y = \|P_{[q_3]}y\|^2. \tag{6}\label{6}
\end{align}
Here $P_My$ stands for the projection of $y$ onto the space $M$, and we use $[v_1, v_2, \ldots, v_m]$ to denote the space spanned by vectors $v_1, v_2, \ldots, v_m$.
Similarly, one can show that
\begin{align}
SSR(X_2|X_1) = y'\tilde{q}_3\tilde{q}_3'y = \|P_{[\tilde{q}_3]}y\|^2, \tag{7}\label{7}
\end{align}
where $\tilde{q}_3$ is the third column of the $\tilde{Q} := \begin{bmatrix} q_1 & \tilde{q}_2 & \tilde{q}_3\end{bmatrix}$ in the QR decomposition of $\tilde{X} = \begin{bmatrix} e & x_1 & x_2 \end{bmatrix} = \tilde{Q}\tilde{R}$.
With these preparations, suppose that
- $y$ is highly correlated with both $x_1$ and $x_2$.
- $x_1$ and $x_2$ are highly correlated.
Condition 1 implies that both $\|P_{[q_2]}y\|$ and $\|P_{[\tilde{q}_2]}y\|$ are big (whence $\|P_{[q_2, q_3]}y\| \geq \|P_{[q_2]}y\|$ is big), while condition 2 implies both $\|P_{[q_3]}y\|$ and $\|P_{[\tilde{q}_3]}y\|$ are small. While the first implication is straightforward, the second implication needs elaboration: without loss of generality, let's show that $\|P_{[q_3]}y\|$ is small. To this end, note that $[e, x_2] = [q_1, q_2]$ and $[e, x_2, x_1] = [q_1, q_2, q_3]$, it follows that
\begin{align}
\|P_{[q_3]}y\|^2
= \|P_{[e, x_2, x_1]}y\|^2 - \|P_{[e, x_2]}y\|^2
= \|P_{[e, x_2]^\perp}\left(P_{[e, x_2, x_1]}y\right)\|^2,
\end{align}
where $[e, x_2]^\perp$ is the orthogonal complement of $[e, x_2]$. Under condition 2, it is easy to see that $[e, x_2, x_1] \approx [e, x_2]$, whence the projection of $P_{[e, x_2, x_1]}y$ onto $[e, x_2]^\perp$ is very close to zero, hence $\|P_{[q_3]}y\|^2$ must be small. Similarly, $\|P_{[\tilde{q}_3]}y\|^2$ is small. In summary, we showed that under condition 1 and condition 2, $\eqref{5}$ is big (hence $F_0$ in $\eqref{4}$ is big, which results in significant $F$-test outcome) and $\eqref{6}$ and $\eqref{7}$ are small (hence $F_1$ in $\eqref{3.1}$ and $F_2$ in $\eqref{3.2}$ are small, which results in insignificant $t$-test outcomes).
To conclude the discussion of the multicollinearity cause, let me point out that the mere multicollinearity without high correlation between $y$ and predictors would not guarantee the significant $F$-test (i.e., the lack of condition 1 above). Many existing answers attributed the paradox to (oversimplified) multicollinearity, which is technically insufficient (remember that multicollinearity is a property of the design matrix $X$ only that has nothing to do with the response).
Another cause of this paradox is as described by the second reason of Jeromy Anglim's answer, and can also be explained using the framework built earlier. This actually corresponds to the scenario
\begin{align}
& \max(\|P_{[q_3]}y\|^2, \|P_{[\tilde{q}_3]}y\|^2) \leq MSE \cdot q_1^*, \\
& \|P_{[q_2]}y\|^2 + \|P_{[q_3]}y\|^2 > 2MSE \cdot q_2^*. \tag{8}\label{8}
\end{align}
Since we have the freedom of controlling the magnitudes of $P_{[q_2]}y$ and $P_{[q_3]}y$ (from the counterexample construction perspective), for $q_1^* < 2q_2^*$, there are countless concrete examples such that $\eqref{8}$ holds.