Why specify the state of a particle in terms of position and momentum not velocity? Often a particle's state is expressed in terms of position and momentum. Why not position and velocity? Momentum has a connection to the particle's mass which I wouldn't say is so important to the particles "state" since it stays the same.
 A: tl;dr: In classical mechanics, specifying a particle's state in terms of momentum is equivalent to specifying it in terms of velocity, but the specification in terms of momenta often has computational advantages. In quantum mechanics, there is no velocity to speak of.
In classical (discrete) mechanics, a particle always has a generalized position $q = (q^1,\dots,q^n)$. Since the equations of motion typically require additional initial data to be uniquely solved for a trajectory $q(t)$, the state of a particle is not fixed by that, but we require $n$ additional data points to fix the state of the system.
In Lagrangian mechanics, we indeed take the generalized velocities $\dot{q} = (\dot{q}^1,\dots,\dot{q}^n)$ as that additional data, so that the $2n$-tuple $(q,\dot{q})$ describes the state completely. Along a trajectory that is a solution to the equations of motion, $\dot{q}(t) = \frac{\mathrm{d}}{\mathrm{d}t}q$ holds, i.e. $\dot{q}$ actually describes the velocity along the trajectory. The equations of motion are $n$ second-order differential equations, the Euler-Lagrange equations
$$ \frac{\partial L}{\partial q^i} - \frac{\mathrm{d}}{\mathrm{d}t}\frac{\partial L}{\partial\dot{q}^i} = 0$$
for the Lagrangian $L(q,\dot{q},t)$.
In Hamiltonian mechanics, the generalized momenta $p = (p_1,\dots,p_n)$ are used instead of the velocities, and the equations of motion are $2n$ first-order differential equations
$$ \dot{p} - \frac{\partial H}{\partial q} \quad \wedge \quad \dot{q} = \frac{\partial H}{\partial p}$$
where the Hamiltonian $H(q,p,t)$ is related to the Lagrangian by a Legendre transformation. If the transformation is singular, care must be taken so that the gauge symmetries of the Lagrangian are properly translated into constraints of the Hamiltonian.
There even exists a mixed formalism, Routhian mechanics, where some momenta and some velocities are used.
Therefore, classically, there is no universal reason to prefer momenta over velocities - both give equations of motion, and both require the same amount of variables to specify a state uniquely. However, for Hamiltonian systems, it is easier to get useful conservation laws. For instance, if a coordinate $q^i$ does not appear in the Hamiltonian, the corresponding momentum is conserved, and we effectively have one equation less to solve. In the Lagrangian formalism, conservation of momentum does not reduce the amount of variables or equations we are dealing with. Thus, one might prefer using momenta over position. Additionally, one might consider first-order equations "more solvable" than second order equations, and the are very useful special sets of positions and momenta called action-angle variables which have no Lagrangian analogue.
Furthermore, the Hamiltonian picture is the one amenable to quantization. Quantum mechanics does not have well-defined trajectories $q(t)$, so the notion of a velocity does not make sense. On the contrary, the momentum operator can still be defined as relating to the position operator in the same way as in Hamiltonian mechanics, by replacing the classical Poisson bracket by the quantum commutator of operators.
A: In Lagrangian mechanics the system is indeed specified by the configuration (positions) and their time rates (velocities) and your equations of evolution (Euler Lagrange equations) end up being second order equations for the configuration (positions).
In Hamiltonian mechanics you specify your system as a point in phase space (a combination of position and canonical momentum). And it is canonical momentum (which is not conserved, so the comments are terrible terrible answers which is why comments shouldn't be trusted for answers because comments can't be down voted) that appears in the Hamiltonian system.
And now the evolution of the Hamiltonian system is a first order evolution on the phase space.
And the canonical momentum isn't so directly related to the particle's mass. It, the canonical momentum, could depend on an external vector potential if there are velocity dependent forces acting on the particle.
And if you are asking about quantum mechanics, that is closer to Hamilton-Jacobi theory than to Hamiltonian mechanics per se, and Hamilton-Jacobi theory has a whole family of phase space positions.
And if you want Heisenberg Picture QM then you want mechanics in Poisson bracket form so you can go to commutators from Poisson brackets.

So [...] in classical mechanics it is a matter of often finding solutions more easily because instead of two variables mass and velocity that have a connection you can often get away with just one, momentum?

No. Firstly, the momentum in a state is canonical momentum which is 100% completely different than $m\vec v$/particularly if there are external forces that depend on velocity (such as magnetism).
And it isn't about being easy. Its about how when you use the correct momentum (not $m\vec v$) then the volume is conserved. Which allows you you discuss experimental uncertainty correctly with dynamics because you choose the state where the dynamics are a first order dynamics that respects experimental uncertainty correctly.

And in quantum mechanics mass and velocity aren't only connected but they always represent themselves as only momentum?

Again, no. The word momentum is a last name. When someone says the word momentum they are being vague. Do they mean mechanical momentum e.g. $m\vec v$? Do they mean field momentum? Do they mean total mechanical momentum, i.e. $m_1\vec v_1+m_2\vec v_2+\dots+m_n\vec v_n$? Do they mean the sum of field momentum and total mechanical momentum? Do they mean canonical momentum? You can only tell from context if they didn't use the full expression, just like if someone only uses a last name then without context you don't know who they are talking about.
When someone says a state, they mean canonical momentum. For some systems the canonical momentum equals the mechanical momentum and that might be why some people don't bothering mentioning which. But its to avoid switching between two things.
Like if you hung a mass on a strong and looped the string over a pulley. You might say the string on the other side is a force of weight. Its a force of tension, which just happens to equal the weight (in magnitude, and when the string has little mass itself). But they are actually different things that happen to be equal in that situation.
So the momentum in a state is canonical momentum. And its used because that first order dynamics will preserve volume in phase space (which has twice as many dimensions as configuration space, which itself has n times as many dimensions as physical space when you have n particles) , so volume in phase space is a physical thing that is conserved. And so its good for statistics and good for describing statistical uncertainty, repeated measurements of systems, and the dynamics of the statistical prediction.
And its good at that for classical mechanics. So when we made quantum mechanics we make it that same way. With a canonical momentum. And a configuration space with n times as many dimensions as physical space.
