Just from Playing FFX1, I would guess that they create an approximate destination point that they pass to the other players. Having played sitting next my friend (both on separate PC's) It seemed like it was just guessing where I was going and feeding the info to his PC. When it got the guess wrong it would send some message telling his PC that my avatar had to move more quickly to adjust for my incorrect position.

for online FPS movement I'd recommend the Gaffer's article. It's the way Counterstrike, Quake3, ect... work out the player prediction and movement.

http://www.gaffer.org/game-physics/networked-physics

Well I will tell you how we handle this problem. The game is an update of Gore: Ultimate Soldier. If you have the game, you can see the real time cause and effect of changing the values I will be referring to.

We use 4 values to determine the network part. Here they are with their values:
Bandwidthin 15000 <-- default for a cable connection
Bandwidthout 15000 <-- default for a cable connection
Packetrate 30 / second
Packetsize 250

In this game you can change these varibles to what ever you want which is great for a developer but bad for hacking reasons.

The packet includes the player, their starting point, their direction of travel, their time (this is the time the up key is pressed for) and their speed.

We set each playermodel to have its own speed. Some games just use one speed for every class. As you can see the server knows where the player will end up based on this calculation.

several ways :

1) RTS system / old LAN quake system.
- gather inputs.
- send inputs to the server
- server calculates the position
- server sends the position back to the client

advantage : simple to code, server has complete authority over the client.
disadvantage : need to send packets frequently, and you will have perceived lag on the clients.

inputs sent every frame or bundled and sent a fixed rate (1/20th second). The less frequently you send, the more preceived lag you will get, but you will incur less UDP overheads (less bandwidth usage).

2) Do the modern FPS way. (Gaffer's article).
- gather inputs.
- run predicted physics on client.
- send prediction result and inputs to the server.
- server runs a simulation and check if the position / velocity he calculates is consistent with the client result.
- if not, send a correction packet to force the client to what the server says he should be. Typically, client position is rolled back to the correction packet sequence number and the prediction re-run from that point on.

inputs are typically sent at a fixed rate, say every 1/20th of a second (cl_cmdrate). Usually caches the input results over several frames and send a bundle of inputs to the server and duplicate packets to combat packet loss (cl_dup).

advantage : cheat detection, server has authority over the client position, no perceived lag in the client inputs since he runs a prediciton algorithm on his side. 99% of the time, the correction will not be required. That system can be build upon algorithm 1) if the input lag really affects the gameplay.

disadvantage : a bit more complex to write, server has complete authority over the client. Client will wobble when the server calculate a different result (that's when you collide with another player for example).