TL;DR: In classical point mechanics, (on-shell) degrees of freedom$^1$ (DOF) are the number of initial conditions needed divided by 2.
Perhaps this is simplest to explain via an example: A 1D simple gravity pendulum with Lagrangian
$$L(\theta,\dot{\theta}) = \frac{m}{2}\ell^2 \dot{\theta}^2 + mg\ell\cos(\theta)$$
has one DOF, $\theta$, although its solution $\theta=\theta(t)$ has two integration constants. Here, the generalized coordinate $\theta$ is the angle of the pendulum; $\dot{\theta}$ is the (angular) velocity; and $p_{\theta}:=\frac{\partial L}{\partial\dot{\theta}}=m\ell^2\dot{\theta}$ is the (angular) momentum. Furthermore, the configuration space $M\cong\mathbb{S}^1$ is one dimensional with one coordinate $\theta$. The tangent bundle $TM$ of the configuration space with two coordinates $(\theta,\dot{\theta})$ and the phase space $T^*M$ with two coordinates $(\theta,p_{\theta})$ are both two dimensional spaces. In other words, it takes two coordinates to fully describe the instantaneous state of the pendulum at a given instant $t$, i.e. two initial conditions.
So, to answer the main question: No, the corresponding velocity (or momentum in the Hamiltonian formulation) is not counted as a separate DOF.
For generalizations to field and gauge theory, see e.g. this Phys.SE post.
References:
- Landau & Lifshitz, Mechanics: see e.g. first page of Chapter 1 or first page of Chapter 2;
- H. Goldstein, Classical Mechanics: see e.g. page 13 or first page of Chapter 8 in both 2nd and 3rd edition;
- J.V. Jose and E.J. Saletan, Classical Dynamics: A Contemporary Approach: see p.18;
- Wikipedia, either here or here.
--
$^1$ Exception: In the context of the equipartition theorem the DOF is conventionally the number of phase space variables that appear quadratically in the Hamiltonian.