We compute the (unbounded) Newton-Okounkov body of the Hilbert scheme of points on $\mathbb C^2$. We obtain an upper bound for the Newton-Okounkov body of the Hilbert scheme of points on any smooth toric surface. We conjecture that this upper bound coincides with the exact Newton-Okounkov body for the Hilbert schemes of points on $\mathbb P^2$, $\mathbb P^1\times\mathbb P^1$, and Hirzebruch surfaces. These results imply upper bounds for the effective cones of these Hilbert schemes, which are also conjecturally sharp in the above cases.