With suitable boundary conditions, the decomposition is unique. Without them, it's not.
Suppose that $(\phi,{\bf G})$ and $(\phi',{\bf G}')$ are two different decompositions for the same function. Then
$$
\nabla(\phi-\phi')+\nabla\times({\bf G}-{\bf G}')=0.
$$
Take the divergence of both sides to find that
$$
\nabla^2(\phi-\phi')=0.
$$
So for any two distinct decompositions, the scalar field $\phi$ must differ by a harmonic function $f$ (that is, one with $\nabla^2f=0$). Moreover, any harmonic function will work -- that is, there will be a way to choose a ${\bf G}'$ to go along with this $\phi'$. To see this, note that we have to choose ${\bf G}'$ to satisfy
$$
\nabla\times({\bf G}'-{\bf G})=\nabla f.
$$
The right side of this expression is divergence-free (because it's $\nabla^2f$), and any divergence-free vector field can be expressed as the curl of some other divergence-free vector field, so ${\bf G'}-{\bf G}$ exists.
(A couple of notes: This latter fact is the one that lets us define the vector potential for a given magnetic field, specifically in Coulomb gauge. To be honest, I don't remember the proof that there exists a function ${\bf G}$ whose curl is ${\bf B}$ for any divergence-free ${\bf B}$. I do remember how you show that, having gotten such a ${\bf G}$, you can make it divergence-free: Just subtract off $\nabla q$ where $\nabla^2q=\nabla\cdot{\bf G}$. The new ${\bf G}$ will have the same curl as the old one and will be divergence-free.
One other thing: complications arise if the domain we're considering isn't simply connected. Let's say it is.)
So the answer is that, to make the decomposition unique, you have to impose strong enough boundary conditions to make it so that no harmonic functions exist. For a compact domain without boundary (such as the surface of a sphere), you don't need any boundary conditions: there are no non-constant harmonic functions on such domains. (Slick proof of this: you can prove that harmonic functions never have local maxima or minima, but a nonconstant function on such a domain must have them -- in particular, it must have a global maximum and a global minimum somewhere.)
For a compact region with boundary, you need to specify either $\phi$ or the normal component of $\nabla\phi$ on the boundary. For good old infinite space, you need to specify that $\phi$ approach zero (or some other given function) as you tend to infinite distance.
It's easy to check that without such boundary conditions, you get into trouble. For instance, take the functions
$$
\phi=x, {\bf G}=z\hat{\bf j}.
$$
They give rise to
$$
{\bf H}=\nabla\phi+\nabla\times{\bf G}=\hat{\bf i}-\hat{\bf i}=0.
$$
So this pair can be added to any Helmholtz decomposition without changing the original vector field.
