Any observable $H$ in classical mechanics defines a flow of states by regarding it as a Hamiltonian. This flow acts on observables $f$ by $df/dt = \{H,f\}$ (this is Hamilton's equation). The idea of a complete set of observables is that it is a set for which any observable with constant flow for all members of the set (ie. Poisson commute with the set) is constant. Intuitively, these flows move all over the phase space, so if $f$ is nonconstant, the flow of $f$ along one of the observables in the complete set can detect this.

I don't think that this means the set of observables can uniquely determine states, though I am having a hard time coming up with a low dimensional counterexample. In other words, the complete set does not have to form a set of coordinates for the phase space.

Any observable $H$ in classical mechanics defines a flow of states by regarding it as a Hamiltonian. This flow acts on observables $f$ by $df/dt = \{H,f\}$ (this is Hamilton's equation). The idea of a complete set of observables is that it is a set for which any observable with constant flow for all members of the set (ie. Poisson commute with the set) is constant. Intuitively, these flows move all over the phase space, so if $f$ is nonconstant, the flow of $f$ along one of the observables in the complete set can detect this.

These functions don't have to form coordinates.

EDIT: To complement QMechanic's counterexample, here is a compact counterexample: consider the 2-sphere with its ordinary symplectic form and the functions $\mathrm{cos} 2\theta$, $\mathrm{sin}\phi$, and $cos \phi$, where $\theta$ is the polar angle, and $\phi$ is the azimuthal angle. These are symmetric accross the equator, so they don't distinguish points, but it is pretty clear that they are a complete set.