Separable states Let $U$ and $V$ be state spaces. By one of the axioms of QM we can describe the combined system as $U \otimes V$. If $U$ has basis $\{|\phi_1\rangle, \dots, |\phi_n \rangle\}$ and $V$ has basis $\{|\psi_1\rangle,\dots,\psi_m\}$, then $U \otimes V$ has basis of the form $|\phi_i \rangle \otimes |\psi_j \rangle$ where $i$ goes from $1$ to $n$ and $j$ from $1$ to $m$.
A state $| s \rangle$ in the system $U \otimes V$ is separable if there is a vector $|\phi \rangle$ in $U$ and $|\psi \rangle$ in $V$ such that
$$
|s\rangle = |\phi \rangle \otimes |\psi \rangle
$$
If a state is not separable, then it is said to be entangled.
Now, the other way around: given an arbitrary state $|g\rangle \in U \otimes V$ it's not obvious to me how to verify if it's entangled or not. That is, how does one about proving that this $|g\rangle$ state is not separable?

As far as I'm aware this is an open problem. There are multiple measures that do measure degrees of entanglement, see for instance 
Plenio, M.B.; Virmani, S. An introduction to entanglement measures. Quant. Inf. Comp. 2007, 7, 1
There is an easy way to verify if a state is maximally entangled: if the partial trace on both components gives you the maximally entangled state (this is kind of the definition of a maximally entangled state).
