Variational calculus on a vector bundle E equipped with a structure of a general algebroid is developed, together with the corresponding analogs of Euler-Lagrange equations. Constrained systems are introduced in the variational and in the geometrical setting. The constrained Euler-Lagrange equations are derived for analogs of holonomic, vakonomic and nonholonomic constraints. This general model covers majority of first-order Lagrangian systems which are present in the literature and reduces to the standard variational calculus and the Euler-Lagrange equations in Classical Mechanics for E=TM.