I thought I'd add my intuition for it a few months later. First of all, Alecos' intuition is great in qualitative terms! My post is more of a mathematical intuition (as in, how one would rediscover the formulation of recursive least squares, using only linear algebra).
Denote by $\hat{Y}_t=\beta_t X_t$ the vector (in $\mathbb{R}^t$) of fitted values of $y$. Since the least squares procedure is a projection, we have that
$\langle \hat{Y}_t, X^i_t \rangle = \langle Y_t, X^i_t \rangle$ for $i\in\{1, \ldots, k\}$ and $\hat{Y}_t\in span\{X^1_t, \ldots, X^k_t\}$ ($\langle \cdot, \cdot \rangle$ denotes the inner product of $\mathbb{R}^t$).
Similarly, we have
$\langle \hat{Y}_{t-1}, X^i_{t-1} \rangle = \langle Y_{t-1}, X^i_{t-1} \rangle$ for $i\in\{1, \ldots, k\}$ and $\hat{Y}_{t-1}\in span\{X^1_{t-1}, \ldots, X^k_{t-1}\}$ ($\langle \cdot, \cdot \rangle$ denotes the inner product of $\mathbb{R}^{t-1}$).
We want to relate the two inner products somehow. From the definition of the inner product, it is clear that $\langle Y_t, X^i_t\rangle = \langle Y_{t-1}, X^i_{t-1}\rangle + x^i_t y_t$. Therefore, we get
$\langle \hat{Y}_t, X_t^i\rangle = \langle \hat{Y}_{t-1}, X^i_{t-1}\rangle + x^i_t y_t$. This, I think, is the essential formula.
To express everything in terms of the betas, we substitute in $\beta_t X_t$ for $\hat{Y}_t$ and bear in mind that $X_t = (X_t^1|\ldots| X_t^k)$ and get
$X_t'X_t\beta_t = X_{t-1}'X_{t-1}\beta_{t-1} + x_t'y_t$.
Now we are led to want to relate $X_t'X_t$ to $X_{t-1}'X_{t-1}$. This is easy, $X_t'X_t = X_{t-1}'X_{t-1} + x_t'x_t$. Therefore, we get
$\beta_t = \beta_{t-1} + (X_t'X_t)^{-1}x_t'(y_t-x_t\beta_{t-1})$ (with several intuitions, see Alecos' answer).
We conclude that we have a recursive formulation:
$\beta_t = \beta_{t-1} + (X_t'X_t)^{-1}x_t'(y_t-x_t\beta_{t-1})$.
$X_t'X_t = X_{t-1}'X_{t-1} + x_t'x_t$
The super crisp geometric intuition (why the formula is obvious without computation) is still evading me. Maybe I will return in another six months.