Adding Initial Velocity in the Game Engine
You can add a force to the object by activating an motion actuator.

Ensure the actuator deactivates after applying the initial force (or velocity).
 

When you are working with dynamically added objects it is even simpler. You can set up an initial velocity of the added object.