Let a group G act on a set $X$, and suppose that $x,y \in X$ lie in the same orbit. Prove that $G_y=g^{-1}G_xg$ for some $g \in G$
Ok, lets assume $G$ acts on $X$,where $x,y \in X, g \in G$ and $y=gx$. Let $k \in G_y$. Then, $ky=y$ and
$$(g^{-1}kg)x=(g^{-1}k)(gx)=(g^{-1}k)y=g^{-1}(ky)=g^{-1}y=g^{-1}(gx)=(g^{-1}g)x=x$$
Therefore, $g^{-1}G_yg \subseteq G_x$
Does this logic seem sound? Would I be able to use a similar method to prove the other inclusion?
Yes. Your logic is sound. And, using @David Wheeler's suggestion, here is a slightly more polished answer. For $x,y$ in the same orbit, we have $g(x)=y$ and we want to show that $$gG_xg^{-1}=G_y$$ If $h\in G_x$, then $$\begin{aligned} ghg^{-1}(y)&=ghg^{-1}(g(x)) \\&= gh(x) \\&=g(x) \\&=y \end{aligned}$$ Therefore, $gG_xg^{-1}\subseteq G_y$. Reversing the roles of $x$ and $y$ the same argument provides $gG_yg^{-1}\subseteq G_x$; in other words, $G_y \subseteq gG_xg^{-1}$, completing the proof.