The weights do figure in a major way. The design effect (the ratio of variances for the complex design and an SRS that you are used to power-analyzing) due to unequal weights is customarily written as
$$
{\rm DEFF}_w = \frac{V_{\rm Design}[y]}{V_{\rm SRS}[y]}=1+{\rm CV}^2_w = \frac{n\sum_i w_i^2}{\bigl(\sum_i w_i)^2}
$$
So as a very first approximation, you can compute the expected CV of weights for your study, compute this DEFF, and pro-rate the sample size computed from the simple unweighted analysis by that number. This procedure assumes that the weights are not correlated with your important analysis variables (the outcome itself, the treatment groups, etc.), which may or may not be a reasonable assumption. A more accurate analysis would have to take stratification and other complex sample features explicitly.
As Greg Snow correctly pointed out, a simulation study would indeed be the next logical step in trying to do this with an utmost precision. Doing simulations with unequal probabilities of selection, however, is a fairly complicated business, and if you are new to it, you will likely do it wrong for the first five or so times.