What is my state in the context of Hamiltonian mechanics? I'm only beginning to learn the Lagrangian and Hamiltonian formulations (currently in chapter 9 of Goldstein), so please bear with me if my problem is too elementary.
I can see the point of going from $n$ generalized coordinates $q_i$ and their velocities $\dot q_i$ in the Lagrangian formulation to $2n$ coordinates+momenta $q_i, p_i$ in the Hamiltonian formulation, in that it 


*

*turns the $n$ second order Euler-Lagrange equations to the $2n$ first order Hamilton's equations

*lends mechanics the language of canonical transformations as a tool to simplify equations by making transformations such that momenta/coordinates become cyclic

*leads to connections between symmetries and conserved quantities through looking at the change in Hamiltonian under an "active" infinitesimal canonical transformation


At the end of the day however, what we want is a way to describe the state of a system as a function of time, given physical context (a description of the potential, an understanding of how our generalized coordinates and momenta will "look" in terms of our system, and initial conditions). In the Lagrangian formulation, our state is simply $q_i(t)$, the $n$ coordinates of the system as a function of time. In the Hamiltonian formulation however, we get $2n$ trajectories, $q_i(t)$ and $p_i(t)$.
Are the momentum trajectories redundant? If they aren't, where in our change of formulation did our state space double in size? Why is phase space important for describing state?
 A: *

*OP is comparing $n$-dimensional solutions 
$$t~\mapsto~ (q^1(t), \ldots, q^n(t)) \tag{1}$$ 
to Lagrange eqs. in the Lagrangian formalism with $2n$-dimensional solutions 
$$t~\mapsto~ (q^1(t), \ldots, q^n(t),p_1(t), \ldots, p_n(t)) \tag{2}$$
to Hamilton's eqs. in Hamiltonian formalism, and ponder how there can be a bijective correspondence between the 2 sets of solutions?
Answer: To properly gauge the number of solutions, we should count the number of integration constants. This is  the same in both cases, namely $2n$. 

*Finally, let us address OP's title question (v2): 


*

*In Lagrangian mechanics, an instantaneous state of the system (at some instant $t_0$) is a point  $(q(t_0),v(t_0))\in TM$.

*In Hamiltonian mechanics, an instantaneous state of the system (at some instant $t_0$) is a point $(q(t_0),p(t_0))\in T^{\ast}M$.
Note that there is a bijective map between instantaneous states of the system (at some instant $t_0$) and initial conditions of the system (where $t_0$ is the initial time).

*Finally OP is asking whether the generalized velocities $v^1, \ldots,v^n$, are independent variables or not? This is e.g. explained in my Phys.SE answer here.
