Edit: I've revised the answer to make it more elementary, and to fix the error YACP pointed out (thank you).
Suppose $X\in N_{GL_n(K)}(S_n)$. Then for every permutation matrix $P\in S_n$ we have $XPX^{-1}\in S_n$, so conjugation by $X$ is an automorphism of $S_n$. If $n\ne 2, 6$, then as YACP noted it must be an inner automorphism, i.e. we have some $P'\in S_n$ such that for every $P\in S_n$, $XPX^{-1}=P'P{P'}^{-1}$. Thus $(X^{-1}P')P(X^{-1}P')^{-1}=P$, so $X^{-1}P'\in C_{GL_n(K)}(S_n)$ (the centralizer of $S_n$). Thus $X\in C_{GL_n(K)}(S_n)\cdot S_n$, so all we have to do is find $C_{GL_n(K)}(S_n)$, as $C_{GL_n(K)}(S_n)\cdot S_n\subseteq N_{GL_n(K)}(S_n)$ holds trivially.
Let $\mathcal C$ denote of all matrices (including non-invertible ones) $X$ such that $PXP^{-1}=X$ for all $P\in S_n$. Note that conjugation is linear, i.e. $A(X+Y)A^{-1}=AXA^{-1}+AYA^{-1}$ for any $A,X,Y\in M_{n\times n}(K)$, so $\mathcal C$ is closed under addition. Conjugation also respects scalar multiplication, i.e. $AcXA^{-1}=cAXA^{-1}$, so $\mathcal C$ is closed under scalar multiplication. Recall that $M_{n\times n}(K)$ is a vector space over $K$, so this makes $\mathcal C$ a subspace of $M_{n\times n}$. The use of $\mathcal C$ is that $C_{GL_n(K)}(S_n)=\mathcal C\cap GL_n(K)$, yet unlike $C_{GL_n(K)}(S_n)$ it is a vector subspace, and vector subspaces are nice to work with.
It is easy to see that $\mathcal C$ contains diagonal matrices $D$ with constant diagonal, as well as all matrices $M$ such that the entries $m_{ij}$ are the same for all $i,j$. Since $\mathcal C$ is a vector subspace, this means it contains all sums of these matrices as well. We want to show that every matrix in $\mathcal C$ can be written as $D+M$ where $D$ and $M$ are as above. If $X\in \mathcal C$ then we can subtract a diagonal matrix $D$ and a matrix $M$ of the second kind to get the upper left and right entries to be $0$:
$$X-D-M=\begin{pmatrix} 0 & x_{12} & \cdots & x_{1n-1} & 0\\
x_{21} & x_{22} & \cdots & x_{2n-1} & x_{2n}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
x_{n1} & x_{n2} & \cdots & x_{nn-1} & x_{nn}\\
\end{pmatrix}$$
Call this matrix $X'$; we wish to show $X'=0$. Exchanging the second and last column must be the same as exchanging the second and last row, and since the first action switches $x_{12}$ and $x_{1n}$ while the second leaves the first row unchanged we have $x_{12}=x_{1n}=0$. Continuing in this manner we see that the whole first row is $0$. Exchanging the first and second row is the same as exchanging the first and second column, so the whole second row must be $0$ as well. Continuing in this manner we get that $X'=0$ as desired. Thus $\mathcal C$ is the set of matrices of the form $D+M$, i.e. with $a$ on the diagonal and $b$ off the diagonal.
$C_{GL_n(K)}(S_n)$ is the set of such matrices with nonzero determinant. Let $X\in \mathcal C$ have entries $a$ on the diagonal and $b$ off it. Clearly if $a=b$ then the determinant is $0$, so suppose $a\ne b$. Then we can write $X=(a-b)(I_n+cr)$ where $c$ is a column consisting entirely of $1$'s and $r$ is a row consisting entirely of entries $\frac{b}{a-b}$. By Sylvester's Determinant Theorem the determinant of this is $(a-b)^n(1+rc)$, and $rc=\frac{nb}{a-b}$, which gives us $\det(X)=(a-b)^{n-1}(a-b+nb)$. Thus for any $X\in \mathcal C$, $\det(X)=0$ iff either $a=b$ or $a=(1-n)b$.
Putting this all together, we get that
$$N_{GL_n(K)}(S_n)=\left\{\begin{pmatrix} a & b & \cdots & b \\
b & a & \ddots &\vdots \\
\vdots &\ddots & \ddots & b\\
b & \cdots & b & a\\
\end{pmatrix}P: a\neq b, a\neq (1-n)b, P\in S_n \right\}$$
In GAP (which is also tagged) there are two possibilities. One could either act on cosets for both subgroups, or one could combine the two actions to a subdirect product.
As an example, lets take the actions of $S_4$ on the cosets of $S_3$ and of $V_4$:
gap> G:=SymmetricGroup(4);;
gap> H1:=SymmetricGroup(3);;H2:=Socle(G);;StructureDescription(H2);
"C2 x C2"
In the first example we simply concatenate the lists of costs as domain, and act on these by right multiplication (GAP always acts from the right and uses right cosets):
gap> cos:=Concatenation(RightCosets(G,H1),RightCosets(G,H2));
[ RightCoset(Sym( [ 1 .. 3 ] ),()), RightCoset(Sym( [ 1 .. 3 ] ),(1,4)),
RightCoset(Sym( [ 1 .. 3 ] ),(1,4,2)), RightCoset(Sym( [ 1 .. 3 ] ),(1,4,
3)), RightCoset(Group([ (1,4)(2,3), (1,2)(3,4) ]),()), RightCoset(Group(
[ (1,4)(2,3), (1,2)(3,4) ]),(3,4)), RightCoset(Group(
[ (1,4)(2,3), (1,2)(3,4) ]),(2,3)), RightCoset(Group(
[ (1,4)(2,3), (1,2)(3,4) ]),(2,3,4)), RightCoset(Group(
[ (1,4)(2,3), (1,2)(3,4) ]),(2,4,3)), RightCoset(Group(
[ (1,4)(2,3), (1,2)(3,4) ]),(2,4)) ]
gap> act:=ActionHomomorphism(G,cos,OnRight,"surjective");
<action epimorphism>
gap> p:=Image(act);
Group([ (1,2,3,4)(5,10)(6,9)(7,8), (2,3)(5,6)(7,9)(8,10) ])
gap> Orbits(p,MovedPoints(p));
[ [ 1, 2, 3, 4 ], [ 5, 10, 6, 8, 9, 7 ] ]
In the sectond version, we constrcut the two permutation actions separately:
gap> p1:=Image(FactorCosetAction(G,H1));
Group([ (1,2,3,4), (2,3) ])
gap> p2:=Image(FactorCosetAction(G,H2));
Group([ (1,6)(2,5)(3,4), (1,2)(3,5)(4,6) ])
Now, we can combine the generator lists on disjoint domains:
gap> diag:=SubdirectDiagonalPerms(GeneratorsOfGroup(p1),GeneratorsOfGroup(p2));
[ (1,2,3,4)(5,10)(6,9)(7,8), (2,3)(5,6)(7,9)(8,10) ]
gap> p:=Group(diag);
Group([ (1,2,3,4)(5,10)(6,9)(7,8), (2,3)(5,6)(7,9)(8,10) ])
If you want to keep the connection better, you could instead use the formal embeddings into a direct product:
gap> d:=DirectProduct(p1,p2);
Group([ (1,2,3,4), (2,3), (5,10)(6,9)(7,8), (5,6)(7,9)(8,10) ])
gap> emb1:=Embedding(d,1);;emb2:=Embedding(d,2);;
gap> gens1:=GeneratorsOfGroup(p1);;gap> diag:=List([1..Length(gens1)],x->Image(emb1,gens1[x])
> *Image(emb2,gens2[x]));
[ (1,2,3,4)(5,10)(6,9)(7,8), (2,3)(5,6)(7,9)(8,10) ]
gap> gens2:=GeneratorsOfGroup(p2);;
gap> diag:=List([1..Length(gens1)],x->Image(emb1,gens1[x])
> *Image(emb2,gens2[x]));
[ (1,2,3,4)(5,10)(6,9)(7,8), (2,3)(5,6)(7,9)(8,10) ]
Best Answer
You have an embedding $G\to S_q$, so you may consider $G$ to be a subgroup of $S_q$. Your group $G$ contains a normal subgroup $K$ of order $q$, and this is generated by an element of order $q$ in $S_q$, $\sigma $ say. Then $\sigma$ is a cycle of length $q$ (since these are the only order $q$ elements in $S_q$). All $q$-cycles are conjugate in $S_q$. Thus by replacing $G$ by a conjugate subgroup one may assume that $\sigma$ is your favourite $q$-cycle $(1\,2\,\cdots\,q)$. Then $K=\left<\sigma\right>$. But $K$ is normal in $G$; therefore $G$ is contained in the normaliser of $K$ within $S_q$.