In the answer below I will not go into relation between Lagrangian and Hamiltonian formalism for the case of constrained systems but will simply restrict to the meaning of constraints (the way I understand it) in Hamiltonian formalism :-
Suppose you are given with a phase space $P$ with variables $(q_1,..,q_n;p_1,..,p_n)$.
Ordinarily one deals with "unconstrained systems". Which means you are only given with a Hamiltonian $H$; and all solutions to equations of motion are allowed. That is there is no restriction on dynamics.
For a constrained system, besides the Hamiltonian $H$ you also have a set of constraint
equations :
$\tag{1}\phi_k(q_1,..,q_n;p_1,..,p_n)=0,\quad k=1,...,m.$
along with the conditions
$\{\phi_i,H\} =0\quad\mbox{on the surface of constraints for all $i=1,...,m$}\tag{2}$
What it means it that now you have to restrict yourself to the dynamics on the surface (i.e. submanifold) in phase space defined by (1). Conditions (2) make sure that constraints are consistent with the dynamics, i.e. if you begin from a point $(q_{i0},p_{i0})$ on the surface of constraint then its time evolution too would lie on the surface.
Now (to the extent I understand it) idea is to differentiate between those constraints which do not pose much problem and can be eliminated (called second class constraints), as compared to those which are somewhat more difficult to deal with (first class constraints). The procedure to define them is as follows:
Find maximal subset {$\phi_1,...,\phi_k$} of set {$\phi_1,...,\phi_n$} of constraint functions such that Poisson bracket of any function in {$\phi_1,...,\phi_k$} with a function in {$\phi_1,...,\phi_n$} is linear combination (with coefficients any arbitrary functions of $p_i,q_i$) of functions $\phi_1,...,\phi_n$. Constraints corresponding to {$\phi_1,...,\phi_k$} are called first class constraints while those corresponding to {$\phi_{k+1},...,\phi_n$} are called second class constraints.
Dirac showed that surface of constraint defined by second class constraints {$\phi_{k+1},...,\phi_n$} is a symplectic submanifold $M$ of phase space $P$. What it means is that (except for the dimension) locally $M$ would look just like phase space $P$ (if you choose right coordinates) and so dynamics on it can be studied like in usual phase space without constraints.
So one can simply eliminate second class constraints by restricting to $M$ as the new phase space, and the rest of functions {$\phi_1,...,\phi_k$} (restricted to $M$) as new constraints.