What you send is what you need for the client-side prediction to work. i.e. position, velocity, orientation, inputs, some special action buttons (fire, jump, ect). Just be careful because all that adds up to a lot of data if you do it naively.

And BTW, you don't need to send prediction info with every input frame. Just once in a while so the server can correct the client-side prediction.

if I could not actually change my position faster than the simulation ticks, what would be the point of updating the rendering?

You can render an interpolated version of the world. Popular console FPS games may run at 30 or 60 Hz for rendering and physics, but typically runs networking at 10, 12, or 15 Hz.
For a sketch, see the canonical game loop: http://www.mindcontrol.org/~hplus/graphics/game_loop.html

But interpolation (or extrapolation) for the player himself, surely that must be noticeable

Old versions of Quake ran the physics at whatever your screen refresh rate was.
The end result was that the physics simulation would let you reach certain ledges/heights when your frame rate was high, but not when it was low.
This is not a good way to make the game fair in multiplayer :-)

Every game is different. That being said, good defaults are to:
- fix your simulation time step
- run input and simulation at 60 Hz (good initial estimate)
- send packets at 20 Hz
- render the scene unlocked from physics -- your choice if you want to interpolate and render faster than physics, or stop at 60 Hz

You can also run input faster than physics, but queue input for the next simulation tick. If you update the *camera* (for turning) faster than simulation, that will not affect simulation, and thus will let you appear to give a faster response time to input at high frame rates, while still getting all the benefits of a fixed simulation rate.

- run input and simulation at 60 Hz (good initial estimate)
- send packets at 20 Hz

So would I just send 3 input states per packet, or what's the difference between these two rates?

Less packet overheads (in UDP anyway).

So would I just send 3 input states per packet, or what's the difference between these two rates?

Yes. Additionally, when receiving the packets, you would queue them for processing -- not just apply all three at the same time step.

This means that the latency introduced by networking is BOTH the batching latency (because the packets are queued on receipt) AND the transmission latency. This is a fact of life, pretty much :-) It's possible to build networked games that send all the packets all the time, and it may provide slightly lower overall latency, at the expensive of significantly higher server overhead. Additionally, you need to be able to compensate for transmission latency anyway, and thus you might as well use that same mechanism to also compensate for batching latency. The server-side overhead of high packet rates is significant!