It's not that the final solution looks like that. Rather, you are looking for all the solutions of that form (normal modes) for two reasons:
So first you work out the normal modes by assuming a solution like the one you wrote there. Then you write a system of equations that says the coordinates are a linear combination of the normal modes.
By evaluating this set of equations at some instant in time, and equating it to a set of initial conditions, you can solve for the amplitude of each normal mode. Here's a complete worked out example.
It is often enough to know what the normal frequencies are, in order to predict attributes like the absorption spectrum of a molecule.
* Your equation has this form: $\frac{d^2\vec x}{dt^2}=A\vec x$. By diagonalizing the symmetric matrix A, you can write it as a diagonal matrix $D$ in a different basis: $A=CDC^T$ ($C$ is the matrix that takes coordinates in the new basis and gives you positions in the old one). Multiplying the original equation by $C^T$ on the left and using $C^TC=\mathbb I$, you get $\frac{d^2}{dt^2}C^T\vec x=DC^T\vec x$. Calling $\vec y=C^T\vec x$ the normal coordinates, you now have a set of uncoupled differential equations: $\frac{d^2y_n}{dt^2}=D_ny_n$. Their solution is $y_n=A_n\sin(\omega_nt+\phi_n)$, with $\omega_n=\sqrt{-D_n}$.
While this proves that you have a basis of normal modes, you don't go through this whole procedure each time. You usually just propose normal mode solutions.