If kinetic energy is a function of the square of velocity, how can gravitiational acceleration be constant? Kinetic energy is defined as: \begin{equation}
E_k = \frac{mv^2}{2}
\end{equation}
Because of the squared velocity term in there, the faster you're going, the more energy it takes to further accelerate.  (This is why it takes longer to get your car from 30 to 60 than from 0 to 30, for example.)
However, unlike normal methods of acceleration that add (more or less) constant energy over time to an object, the force of gravity is defined as imparting a constant acceleration over time to an object. How does that work?  
Does that imply that the faster an object is already moving (in the direction of the mass exerting gravity on the object), the stronger gravity pulls at it?
 A: Assuming a constant gravitational acceleration g, the potential energy of a mass m at a height h is:
$U = mgh$
Now, if the mass is allowed to fall freely from this height, the downward speed $v$ increases linearly with time under the constant acceleration of gravity:
$v = gt$
and thus, the height of the mass decreases with the square of the time:
$\Delta h = -\dfrac{gt^2}{2}$
This is the key.  The force on the mass is constant but the distance through which the force acts, per unit time, is greater at a later time than at an earlier time.
From the above, we get the change in potential energy with time is:
$\Delta U =mg\Delta h =-\dfrac{m(gt)^2}{2} = -\dfrac{mv^2}{2}$
The potential energy lost must (ignoring losses) equal the kinetic energy gained:
$\Delta KE = -\Delta U = \dfrac{mv^2}{2}$
A: Your starting point "normal methods of acceleration [..] add [..] constant energy over time to an object" is not correct. 
A constant force I would classify as "a normal method of acceleration". Such constant force adds constant energy not when applied over a fixed duration, but rather when applied over a fixed distance.
A: One doesn't necessarily need to pull stronger at some object to provide it with greater energy. The amount of energy an object gains or the work done on that object by the force applied is given by $$W=\vec F\cdot\vec s$$ 
where $\vec F$ is the force vector and $\vec s$ is the displacement vector. So you see that one can do more work on an object by simply increasing any one of the two quantities.
In case of gravity, the quantity $\vec s$ increases when an object is moving with greater velocity. This can be said using this equation: $$s =ut+\frac 12at^2$$
where $u$ is the initial velocity and $a$ is the acceleration. So it is clear that an object with greater $u$ will travel a greater distance $s$ in a given time $t$(Because $a$ is constant for any object you take).
Thus the work done on it will be more and it will gain more kinetic energy.
Note: This assumes you are in a constant gravitational field, i.e. you are close to the surface of the earth. So there is a constant gravitational acceleration $g$ downward. In other cases the force $F$ increases too when you move closer to the earth.
