Details on the magnetic field of a linearly polarized electric wave Suppose we are in vacuum and we have an electric field $\vec{E}$ which we assume is simple harmonic wave that propagates through $z$ and is linearly polarized in the $x$-$y$ plane along $x$ i.e. $\vec{E}(t,x,y,z)=E_0\cos(\omega t-kz)\hat{x}$. This function obviously satisfies $\vec{\nabla}\cdot\vec{E}=0$. Now note that $$\vec{\nabla}\times\vec{E}(t,x,y,z)=\frac{\partial}{\partial z}\left( E_0\cos(\omega t-kz) \right)\hat{y}=kE_0\sin(\omega t-kz)\hat{y}=-\frac{\partial \vec{B}}{\partial t}(t,x,y,z)$$
If we integrate this, we get $\vec{B}(t,x,y,z)=B_0\cos(\omega t-kz)\hat{y}+\vec{g}(x,y,z)$ for some $\vec{g}:\mathbb{R}^3\rightarrow\mathbb{R}^3$ and where $B_0=\frac{k}{\omega}E_0$. Now note that $B_0\cos(\omega t-kz)\hat{y}$ has no gradient and therefore $\vec{\nabla}\cdot\vec{B}=0$ implies $\vec{\nabla}\cdot\vec{g}=0$. On the other hand $\vec{\nabla}\times (B_0\cos(\omega t-kz)\hat{y})=\mu_0\epsilon_0\frac{\partial\vec{E}}{\partial t}(t,x,y,z)$, which implies $\vec{\nabla}\times\vec{g}=\vec{0}$. Finally, clearly $B_0\cos(\omega t-kz)\hat{y}$ satisfies the wave equation, which means that $\vec{g}$ must do it too. Since $\vec{g}$ has no time dependence, $\nabla^2\vec{g}=\vec{0}$.
On every source I have seen, the vector field $\vec{g}$ has been taken to be null. From this assumption things such as the perpendicularity between the fields and the direction of propagation are explained. Non the less, non of the three restrictions imply that $\vec{g}$ be null. In particular, $\vec{g}$ could be a constant vector field with any direction and still satisfy Maxwell's equations. 
Is there any way to show that in general E&M waves must be perpendicular and therefore show that $\vec{g}=\vec{0}$? In the case there isn't, what can we say about $\vec{g}$ knowing  $\vec{\nabla}\cdot\vec{g}=0$, $\vec{\nabla}\times\vec{g}=\vec{0}$ and  $\nabla^2\vec{g}=\vec{0}$?
 A: There is no reason for the field to be null. You have correctly identified the properties of another magnetic field that could be the solution of Maxwell's equations that is consistent with electric field you started with - namely a time-independent magnetic field.
The situation is exactly that by which you are reading this answer. EM waves propagate into your eyes, but between you and the screen the space is filled with the Earth's (roughly) time-independent magnetic field.
As CuriousOne completely describes, the reason this works is that you can superpose any solutions to Maxwell's equations and a time-independent magnetic field can be a solution with zero electric field and a Laplacian of zero.
The reason books ignore this, is because you can ignore it. The time-dependent EM wave fields can be considered in isolation from any time-independent E- and B-fields in the "background". Saying that a time-dependent E-field can "produce" a time-independent B-field is not a correct way to think about electromagnetism - the fields co-exist. No SHM E-field is associated with a time-independent B-field - as you confirmed by showing that its curl was zero.
