When do fibre products of smooth manifolds exist?

It suffices for one of the two maps to be a submersion for the fibre product to exist. In fact, if $f$ and $g$ are maps from $X$ to $Y$, the fibre product is the inverse image of the diagonal in $Y times Y$ under the map $f times g : Xtimes X to Y times Y$. So a sufficient condition to have a nice fibre product is that $f times g$ be transverse to the diagonal.

The next best thing to transverse intersection is clean intersection, as Ben has pointed out. Another definition of clean intersection of $A$ and $B$ in $X$ (more easily checked than the one about the local normal form) is that the intersection of $A$ and $B$ is a submanifold $C$, and that the tangent bundle to $C$ is the intersection of the tangent bundles to $A$ and $B$.