I think that calculating the instantaneous velocity as described by Usama is the correct method so long as you can deal with the cumulative error. I would also suggest that you provide regular recalibration to deal with that (like a return to home).
However, if you are trying to calculate velocity the best method would be to use a gyroscope, not an accelerometer.
Gyroscopes were (are?) how submarines navigate underwater. To measure acceleration with gyro sensors it is of course the rate of change of the velocity. V = Vo + at and d = Vo.t + (a.t^2)/2 are your two most important formulas.
Which you choose depends upon your application. I would chose either based on whether my application is more likely to have constant velocity or frequently accelerating and decelerating. Maybe even have both...
I have not experimented with digital gyro sensors but note that there are a couple of Arduino shields available.