How can momentum be increased?
By increasing the velocity of the object.
(If the same object does not have to be used then by using an object with larger mass.)
If the requirement is to increase the momentum of a specific object its mass will likely be fixed. So to give that more momentum you will have to increase its velocity by doing work on it.
If the object can be changed for another object which can be given the same velocity, the initial object can be changed for another with larger mass. Then when the larger mass is given the same velocity it will have a larger momentum than the initial object.
Mathematical explanation for the above.
Momentum = mass × velocity
So for an object of constant mass:
For any directly proportional relationship if one variable increases the other variable increases also (by the same proportion). Therefore, in this case if I want to increase the momentum of an object of constant mass I need to increase the velocity.