Computing the decimation ratio between two m-sequences
I finally asked this question on mathoverflow.net and got a very helpful answer.

The short answer is to follow essentially the following procedure:


Find any root $y_1 \in F_1$ of $p_2(y)$ in the polynomial ring $F_1[y]$ --- these are the polynomials $p(y)$ which have coefficients that are elements in $F_1$ and are themselves polynomials. 
Take the discrete logarithm to determine $j$ such that $x^j = y_1$
Any decimation ratio in the cyclotomic coset of $j$ is a valid decimation ratio.


I've written up a longer description in my blog post which includes the use of a factoring method that partitions $p(y)$ as $p(y) = \gcd(p(y),S(x^ky))\gcd(p(y),S(x^ky)-1)$ where $S(u) = u + u^2 + u^4 + u^8 + \ldots + u^{2^N-1}$, which is mentioned in Lidl + Niederreiter and also in http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/.