Several other answers have addressed ways to automatically and passively dissipate the energy in a highly effective fashion. I'm going to answer the exact question you asked: how long should reverse voltage be applied, if applying reverse voltage is how we're going to do it?
Let's consider the solenoid as an inductor, without the effects of the moving core. Then the goal is to drive the current through the solenoid to zero.

simulate this circuit – Schematic created using CircuitLab
The magnitude of the current assuming that the solenoid has been on for a while is \$I_{\text{on}} = V_{\text{in}}/R\$, because it is determined by the coil resistance and not at all the inductance.
Now suppose we reverse the polarity. This is readily done with a H-bridge as would be done for reversing a motor — a solenoid is electrically the same kind of thing. Then we have applied a step voltage change (of \$2V\text{in}\$) to the solenoid. How do we know how it will respond to this? It's an RL circuit! The step response of such a circuit, in the usual form of “applied voltage was zero at \$t=0\$ and is now a constant \$V\$”, is
$$I(t) = \frac{V}{R}(1 - e^{-(R/L)t})$$
In this case we're considering not going from \$0\$ to some \$V\$ but from \$+V_{\text{in}}\$ to \$-V_{\text{in}}\$, but since this is a linear system it doesn't matter where we start; to use this equation we just need to double the applied voltage. Then the condition we are looking for is when this curve is equal in magnitude to the steady-state on current \$I_{\text{on}}\$, which is the same time as when the actual decreasing current will equal zero. (We could do this with less fiddling by starting from the differential equation \$I = dv/dt\$ and solving it, but I figure reusing existing well-known solutions is a more practical-intuition approach.)
$$
\begin{align*}
\frac{2V_{\text{in}}}{R}\left(1 - e^{-(R/L)t}\right) &= I_{\text{on}} \\
\frac{2V_{\text{in}}}{R}\left(1 - e^{-(R/L)t}\right) &= \frac{V_{\text{in}}}{R} \\
2\left(1 - e^{-(R/L)t}\right) &= 1 \\
2 - 2e^{-(R/L)t} &= 1 \\
e^{-(R/L)t} &= 1/2 \\
-(R/L)t &= \ln 1/2 \\
(R/L)t &= \ln 2 \\
t &= (\ln 2)\left(\frac{L}{R}\right) \\
\end{align*}
$$
That is, you should apply reverse voltage for \$(\ln 2)\left(\frac{L}{R}\right)\$, or about \$0.7\$ times \$L/R\$, seconds.
\$L\$ and \$R\$ can be found from the specifications of the solenoid or, if documentation is not available, using an LCR meter or other methods of measuring inductance and resistance.
However, this theoretical answer makes several assumptions:
- The moving, temporarily-magnetized iron has no effect.
- Your power supply is an ideal voltage source which doesn't blink at this inductive load. (I'd think of having a big decoupling capacitor, sized to store a few times more energy than we're putting into/out of the coil, right next to the input of this drive circuit. That way, the current and voltage surge flows mostly through the capacitor rather than the rest of the supply circuit.)
- The H-bridge or other reversing device is also ideal.
In practice, if you wanted to do it accurately, you would want to apply the reverse voltage until you detect that the current through the coil has hit zero, then open the circuit.
And, in practice, the various passive energy-dissipation circuits posted in other answers are common and better solutions. Instead of dumping the energy into power supply rails, it is dissipated through a large semiconductor voltage drop. Since this can be a higher voltage than the power supply normally uses (on the principle that an inductor will produce as much voltage at its terminals as needed to cause the current to flow), the decay of the current is even faster than using reversed supply voltage.