This is a very general question, perhaps too general for a definitive answer, and as Jack Schmidt pointed out (in a now deleted comment), it is already a delicate question when $\sigma$ is an inner automorphism. There are bad examples (a little different from Jack's) for all symmetric groups of prime degree greater than $3$. If $p$ is a prime, and $G$ is the symmetric
group $S_{p}$, then a Sylow $p$-subgroup $P$ of $G$ is self centralizing of order $p$,
so $N_{G}(P)$ has order dividing $p(p-1)$. In fact the order is $p(p-1)$. Hence the only elements
of order prime to $p$ which normalize a Sylow $p$-subgroup are powers of a $p-1$-cycle.
Such elements (apart from the identity) have a unique fixed point, and all other cycles of equal
length dividing $p-1$. There are many elements of prime order $q \neq p$ in $S_p$ which are not
of this form, for example any element $\sigma$ of prime order $q$ dividing $p-2$.
Another type of example is provided by ${\rm GL}(n,p)$. If we take a prime $q$ such that
$q$ divides $p^{n}-1$ but does not divide $p^{m}-1$ for any $m <n$, then ${\rm GL}(n,p)$
contains an element $\sigma$ of order $q$ which must act irreducibly on the natural module. Hence
$\sigma$ can not normalize any non-trivial $p$-subgroup $P$ of ${\rm GL}(n,p)$, for if it did,
it would stabilize the space of fixed points of $P$, which is proper and non-zero. Note that $P$
can be made as large as desired by making $n$ large enough (though the choice of $q$ will need
to vary).
In a positive direction, this question does relate to some rather deep theorems in finite group
theory. One of these is the Thompson transitivity theorem (which I will call TTT for short).
This can be found in Gorenstein's book Finite Groups (Chelsea). Most theorems of this type (and there are several others) require the presence of larger elementary Abelian subgroups.
A weak form of the TTT states that if a Sylow $q$-subgroup $Q$ of $G$ contains a maximal Abelian normal subgroup $A$ with 3 or more generators, and such that $C_G(a)$is solvable for each non-identity element $a$ of $A$, then all maximal $A$-invariant $p$-subgroups of $G$ are conjugate
via an element of $O_{q'}(C_{G}(A))$ ( $p$ a prime different from $q$). In particular,
the number of such subgroups is prime to $q$. Hence, for example, if we assume $Q$ is $\sigma$-invariant (which we may, possibly after replacing $\sigma$ by
an $H$-conjugate, where $H$ is the semi-direct product $G\langle \sigma \rangle$), then $Q$ will permute the maximal $A$-invariant $p$-subgroups by
conjugation. The number of these is prime to $q$, so the number fixed by $Q$ (under conjugation)
is prime to $q$. Those fixed by $Q$ are the maximal $Q$-invariant $p$-subgroups of $G$. Since
$\sigma$ normalizes $Q$, these are in turn permuted by $\sigma$ under conjugation. Since their number
is prime to $q$, one of them must be fixed by $\sigma$. Hence if $A$ normalizes a non-trivial
$p$-subgroup of $G$, so does $\sigma$.
