I have the double sum
$$ \sum_{n=0}^\infty \sum_{k=1}^n q(k)p(n-k) $$
It's important that $p(s)=0$ whenever $s<0$.
I think it's ok to write
$$ \sum_{k=1}^\infty \sum_{n=k}^\infty q(k)p(n-k), $$ but I'm unsure on this.
My reasoning to get here from the first equation stems from considering that $$ n=0 \text{ means } k\in \{\},$$ $$ n=1 \text{ means } k\in \{1\},$$ $$ n=2 \text{ means } k\in \{1,2\},$$ $$ n=3 \text{ means } k\in \{1,2,3\},$$ and so on, which is equivalent to $$ k=1 \text{ means } n\in \{1,2,3,\dots\},$$ $$ k=2 \text{ means } n\in \{2,3,\dots\},$$ and so on.
Is this exchange of summations and my reasoning for it correct?
You can definitely do that exchange when the double summation converges absolutely, although the reasoning is not quite so immediate (interchanging limit process rarely is). You can prove it by hand (see Apostol's Mathematical Analysis for a proof, although Googling "double summation" should probably be quicker), or quote Fubini's theorem with counting measure (but this is a bit more advanced).
In the case where all $p(k)$ and $q(k)$ are non-negative, the proof by hand is slightly simpler.