There are a millions ways to integrate accelerations over time.
Euler integrations are the simplest: pos+=vel*t.

Look up RK4 (Runge-Kutta 4) on Google and walk into a whole world of integration techniques.

Anyhow, if you only have simple, constant gravity, there is simple scheme you can use. You can store the last time and values the velocity has been manually changed, eg. through collision or other things, as v0 and t0. then, you could do the integration in the following way:

delta_t = t - t0;
pos = v0*delta_t + 0.5*gravity*delta_t*delta_t
and vel = v0 + gravity*delta_t but you dont need it.

aka pos = integral[t0 to t](v0) + integral[t0 to t](integral[t0 to t](gravity))

The above scheme would result in an exact result, no matter the time step size, as there is no more time step for integration. The above equation can be solved for any t. Only t0 and v0 have to be determined in the same manner on different machines in order for the simulation to be consistent.

Well, finally I got it right, thanks to the lot of you. All the solutions were very interesting, and I'll definitely delve deeper into numerical integration later. (I even went to the library and picked up a few math books, I haven't solved a single equation in almost a year. My maths are rusty, to say the least.)

I finally went with OSC:s solution. This is a simple platformer, so I need pretty stable results (not accurate, but independent of time steps) - I for one wouldn't like to be able to reach a certain platform just because my computer isn't fast enough!

Ah, well. Thanks to you all, as always!