Standard algorithms for numerical integration of initial value problems are formulated on vector spaces and make crucial use of that structure; all tangent spaces are identified, allowing averaging of tangent vectors with distinct basepoints, and the update is performed by setting an appropriate difference quotient equal to the resulting average. To extend these algorithms to general manifolds, it is necessary to develop analogs of these operations that are valid and implementable in a nonlinear setting. Lie groups and their tangent or cotangent bundles form a class of manifolds for which particularly natural generalizations of these procedures exist. The group structure can be exploited in the construction of integration schemes generating trajectories lying exactly in the (nonlinear) phase space. The usual weighted averages of vector field evaluations are computed in the Lie algebra or its dual using the natural trivializations of the tangent and cotangent bundles; the resulting update vector is then mapped into the phase space using either the exponential map or an approximate `algorithmic' exponential map. Thus the computation-intensive steps of the algorithm are carried out on a vector space of the same dimension as the phase space; this is particularly advantageous in implicit schemes, where the residual equation must be solved, typically by an iterative method, at each time step. Various combinations of conservation laws (e.g. conservation of energy, momentum, or the symplectic structure) of the original mechanical system can be incorporated in the associated algorithms. An appropriate choice of trivialization can significantly simplify the implementation of such constraints. Group decompositions can be used to design efficient algorithmic exponentials; these decompositions are often suggested by the symmetries of the relevant mechanical system.