If all the terms are positive / negative, it is easy to use the comparison test. The same applies if after say $N$ terms, all the terms of the sequence $a_n$ are of the same sign.
Now suppose we are not in this case, and suppose (without loss of generality) that the first term is positive (otherwise multiply the whole thing by $-1$). Therefore there exists an integer $N_1$ such that for $1 \le n < N_1$, $a_n \ge 0$ and $a_{N_1} < 0$. Since we assume the terms of the sequence are not all negative afterwards, there exists an $N_2$ such that for all $n$ with $N_1 \le n < N_2$, we have $a_n \le 0$ and $a_{N_2} > 0$.
Continuing this pattern by induction, there exists $N_{2k+1}$ such that for $N_{2k} \le n < N_{2k+1}$, $a_n \ge 0$ and $a_{N_{2k+1}} < 0$, and then another integer $N_{2k+2}$ such that for $N_{2k+1} \le n < N_{2k+2}$, $a_n \le 0$, with $a_{N_{2k+2}} > 0$. Therefore you can define a sequence like this : $ \alpha_i = \sum_{n=N_{i-1}}^{N_i - 1} \frac{a_n}{n^p}. $ Note that the serie $ \sum_{i=1}^{\infty} \alpha_i $ converges as well, since $ \sum_{n=1}^{\infty} \frac {a_n}{n^p} = \sum_{i=1}^{\infty} \sum_{n=N_{i-1}}^{N_i - 1} \frac{a_n}{n^p} = \sum_{i=1}^{\infty} \alpha_i. $ Now one can rewrite this series as $ \sum_{i=1}^{\infty} \alpha_i = \sum_{i=1}^{\infty} (-1)^{i+1} |\alpha_i|. $ By Leibniz's criterion, it converges if and only if $|\alpha_i| \to 0$ as $i \to \infty$, therefore it converges. Now define $ \beta_i = \sum_{n = N_{i-1}}^{N_i - 1} \frac{a_n}{n^q}. $ In the same fashion, it is easy to see that $ \sum_{n=1}^{\infty} \frac {a_n}{n^q} = \sum_{i=1}^{\infty} (-1)^{i+1} |\beta_i| $ and since $|\beta_i| \le |\alpha_i|$, $|\beta_i| \to 0$ as $i \to \infty$, and therefore the series on the RHS converges. Note that I am not done yet. To show that this equality actually holds, up to now, I have only shown that the sequence $ S_N = \sum_{n=1}^N \frac{a_n}{n^q} $ has a convergent subsequence, namely $S_{N_i}$. But one easily sees that for $N > N_1$, one can bound $S_N$ from above with a term of the sequence $S_{N_k}$, and similarly from below.
More explicity, write $S_{N_i} \to L$. If $N_{2k} \le n < N_{2k+1}$, then since $a_i \ge 0$, $S_{N_{2k}} \le S_n < S_{N_{2k+1}}$. If $N_{2k+1} \le n < N_{2k+2}$, then since $a_i \le 0$, we have $S_{N_{2k+2}} < S_n \le S_{N_{2k+1}}$. Using $x_n = \min \{S_{N_{2k}}, S_{N_{2k+2}} \}$ one can see that $ \liminf_{n \to \infty} S_n \ge \liminf_{n \to \infty} x_n = \lim_{k \to \infty} S_{N_k} = L. $ A similar argument shows that $\limsup_{n \to \infty} S_n \le L$, which means $\lim_{n \to \infty} S_n = L$.
Hope that helps,
EDIT : I just noticed Leibniz's criterion requires that the sequence is not just positive convergent to $0$ but also decreasing. This is kind of pissing me off. I guess there's a way around it but I don't want to find it. I'll just leave the answer there and say that "in the case where $|a_n|$ is decreasing, our intuition works right".