Examples of Riemannian Submersions
If $E\to B$ is a Riemannian submersion, then so is its restriction onto any open subset, which gives lots of examples of submersions that are not fibrations, e.g. removing a point from $E$ will destroy any fibration structure if there was one.
It is a old theorem of Hermann that any Riemannian submersion $E\to B$ with complete $E$ is a locally trivial fiber bundle (whose structure group need not be a Lie group though). Good sources to learn about Riemannian submersions are Besse's book "Einstein manifolds", chapter 9, and Gromoll-Walschap's recent book "Metric folitations and curvature".
There are submersions $f:\mathbb R^3\to\mathbb R$ such that its fibers are either cylinders or paraboloids which are then not fibrations.
For example, let $f(x,y,z)=\frac{1-r^2}{1+r^2}e^z$ with $r^2=x^2+y^2$. This is the set of level curves of the function in positive quadrant of the $xz$-plane:
In the case $f:M\to N$ is a submersion and both are compact and connected, then, the space is a fibered space (this is, $(M,f,N,f^{-1}(p))$ is). See exercise 33 (Chapter V) of the book of Camacho-Lins Neto (Geometric theory of Foliations).
The idea is that $f^{-1}(p)$ is a compact manifold, and one can see that using the submersion property that it has trivial holonomy. The result then follows from the Stability Theorem.
In general, as mentioned by Mariano Suarez-Alvarez, the result is not true.