The point of the nonlinear medium is to create higher harmonics (here: $\omega_2 = 2\omega_1$), i.e. waves with a multiple of the frequency of the initial wave ($k_1,\omega_1$), which do not vanish when the medium ends. This last statement is of the essence here! But I'll come back to that later.
Now, the electric field of the intial wave ($k_1,\omega_1$) can be described as
$$E_1^{(\omega_1)}(z,t) = E_1 e^{i(k_1 z - \omega_1 t)} + c.c.,$$
where $E_1$ represents the field amplitude, $z$ the propagation direction, $t$ the time and $c.c.$ the complex conjugate.
The nonlinear part of the polarization that creates the second harmonic reads
$$P_{NL}^{(2\omega_1)} = \epsilon_0 \chi^{(2)} E_1^2 e^{2i(k_1 z - \omega_1 t)} + c.c.,$$
where $\epsilon_0$ is the permittity in vacuum and $\chi^{(2)}$ the 2nd order nonlinear susceptibility.
The electric field of the second harmonic is
$$E_2^{(2\omega_1)}(z,t) = E_2 e^{i(k_2 z - \omega_2 t)} + c.c.,$$
where $\omega_2 = 2\omega_1$.
Now, at each point $z$ within the medium the initial wave produces another wave running at $\omega_2 = 2 \omega_1$, but this doesn't imply that every created wave has the same phase! It could be very possible that two different waves running at $\omega_2$ have a phase difference so that they interfere destructively. For the initial wave to consistently feed into the same second wave, it has to propagate at the same speed (phase velocity $v_p$). So
$$v_{p_1} = \frac{\omega_1}{k_1} = \frac{\omega_2}{k_2} = \frac{2\omega_1}{k_2} = v_{p_2},$$
which implies $k_2 = 2 k_1$ or in other words $\Delta k = k_2 - 2 k_1 = 0$. This is the phase matching condition (kudos to dominecf for pointing this out). It shows, that the direction of both the initial and created wave are the same, since $k$ is usually a vector. Using
$$ k_2 = 2 k_1 $$
$$ \Leftrightarrow \frac{\omega_2}{c} n(\omega_2) = \frac{2\omega_1}{c} n(2\omega_1) = 2 \frac{\omega_1}{c} n(\omega_1)$$
$$ \Leftrightarrow n(\omega_2) = n(\omega_1),$$
where $c$ is the speed of light, it's clear, that also the refractive indices match.
It should be highlighted that the phase matching condition not always means that the phase velocities of the waves have to match. The condition for constructive interference has to be satisfied, i.e. $\Delta k = 0$.