If you know how to take $d$th roots, you can use that
$ b^d < 1 + b + b^2 + \cdots + b^d < (1+b)^d $
to get
$ \sqrt[d]{N} < (1+b) < 1 + \sqrt[d]{N} $
which implies that
$ \lfloor \sqrt[d]{N}\rfloor - 1 < b < \lceil \sqrt[d]{N}\rceil[d]{N} $
(If you only care about integer parts of if integer arithmetic is faster) First compute \lfloor\sqrt[d]{N}\rfloor = b'. Check whether for this b' the associated polynomial is bigger or less than $N$. If you underestimated, linearly interpolate between b' and b' + 1. Else interpolate between b' and b'-1.
If you can actually efficiently do floating point arithmetic and can take roots, then you can just linearly interpolate between $\sqrt[d]{N} - 1$ and $\sqrt[d]{N}$.
To do the example given by Ross: Say $N = 10^6$ and $d = 6$. Then $\sqrt[6]{N} = 10$. So we know that $9 < b < 10$.
For the value of 9, the polynomial yields 597871. And for the value of 10 the polynomial is 1,111,111. The linear interpolation gives
$ 9 + \frac{10^6 - 597871}{1111111 - 597871} \sim 9.784 $
with the correct value being around $9.822$.
A different way (again, assuming you know how to take $d$-th roots) is to use the estimate
$ 1 + b + \cdots b^{d-1} + b^d - b^d \sim b^{d-1} $
and
$ (1+b)^d - (1 + b + \cdots b^{d-1} + b^d) \sim (d-1)b^{d-1} $
which gives an estimate of roughly
$ b = \sqrt[d]{N} - 1/d $
(in fact this is an upper bound: see Remark 2 below)
Remark 1 In the demonstration case above this would give $9.833$. This estimate degenerates badly when $\sqrt[d]{N}$ decreases and gets closer to (or less than) $d$, because then the lower order corrections can be numerically larger. So we see that for $\sqrt[d]{N}$ sufficiently larger than $d$, this single estimate should perform better than linear interpolation.
Remark 2 We have also the identity
$ (b+ 1/d)^d = b^d + b^{d-1} + \sum_{k = 1}^{d-2} \frac{1}{d^{d-k}}{d \choose k} b^k $
which, appealing to the fact that $\frac{1}{d^{d-k}}{d \choose k} \leq 1$, you have
$ (b+1/d)^d < 1 + b + \cdots + b^d < (b+1)^d $
Unfortunately, this won't improve the results from the linear interpolation by much as the main difficulty is obtaining a better upperbound other than $(b+1)^d$. For example, we can improve the upperbound slightly by using the fact that
$ \frac{1}{d^{(d-k)/(d-1)}} { d \choose k} \geq 1$
whenever $k >0$. Which implies that
$ \left( b + \frac{1}{d^{1/(d-1)}}\right)^d + 1 \geq b^d + b^{d-1} + \cdots + b + 1 $
which implies that
$ \sqrt[d]{N-1} - \frac{1}{\sqrt[d-1]{d}} < b < \sqrt[d]{N} - \frac{1}{d} $
In the case $N = 10^6$ and $d = 6$. The upper and lower bounds are 9.83333 and 9.30117. Their corresponding polynomial evaluations are around 1006423 and 725477. Linear interpolation gives
$ b \sim 9.83333 - \frac{6423}{1006423 - 725477} \sim 9.8104 $