As other people have pointed out, strictly speaking, you need to know the forces and masses as well as the positions and velocities. You need the masses because Newton's second law for a particle is
$$ F_{net} = \dot{p} $$
Where you can easily find the initial momentum using the formula $p = mv$, which even works relativistically since the previous equation simply becomes
$$ p = \frac{mv}{\sqrt{1 - \frac{v^2}{c^2}}} $$
So you can always find the future momentum (and hence velocity) by integrating the force against time, and you can always find the future position by integrating the velocity against time.
However, knowing the forces means you have to know the laws of physics; more importantly, it requires assuming that forces themselves only depend on positions, velocities, and perhaps particles of the properties themselves.
As it turns out, the forces we observe in classical mechanics follow these rules. So, when people say you just need the initial positions and velocities, what they really mean is that the laws of physics describe many possible ways for objects with given masses and velocities (and charges, spins, etc.) to move, but once you know their positions and velocities, there should in principle be only one way for them to move for the rest of time.
This is a mathematical consequence of the fact that Newton's second law is a second order differential equation in $3 \times N$ variables and hence requires $2 \times 3 \times N$ independent constants, which are provided by positions and velocities, to specify a unique solution.
All tests of classical mechanics reveal this to be true. You do need to know precisely what the positions and velocities of every particle are, so this isn't something that humans can use in practice. But, to the extent that we can measure things precisely, we have always observed nature following this rule. Quantum mechanics is more subtle and outside the scope of this answer.
So, what this tells you is that our assumption that $F_{net}$ can only depend on unchanging properties of the particles themselves along with the velocities and positions of the other particles is consistent with experiment.