Let $G$ be a group and $A\subseteq G$. Consider $H=\{g\in G: gag^{-1}\in A \text{ for all } a\in A\}$. I want to show that that $H$ does not have to be a subgroup of $G$. (Note that for a finite $G$ it always is a subgroup because it suffices to prove closure, which is true in this case).
The material I am using gives the following counterexample, I see why it is a counterexample but I would like to understand intuitively how you can arrive at this result.
Let $G$ be the set of all permutations over $\mathbb{Z}$ and define $S_f=\{n\in\mathbb{Z}:f(n)\neq n\}$ for $f\in G$. Set $A=\{f\in G: S_f\subseteq \mathbb{N}_{>0}\}$. Consider $g\in G$ with $g(n)=n+1$ for all $n$. It's easy to check that $g\in H$. To arrive at a counterexample, we now show that $g^{-1}\notin H$. Let $a\in G$ with $a(1)=2$, $a(2)=1$ and $a(n)=n$ for $n\neq 1,2$, so that $a\in A$. Then $g^{-1}ag(0)=g^{-1}a(1)=g^{-1}(2)=1$. This shows that $0\in S_{g^{-1}ag}$ and thus $g^{-1}ag\notin A$ so that $g^{-1}\notin H$.
As you noted, $H$ is always a closed unter multiplication, thus $H \subseteq G$ is a submonoid. The only way for $H$ to fail to be a subgroup is for it to fail to contain an inverse for one of its elements.
Thus, to find a counterexample we have to ensure that no argument of the form $$gAg^{-1} \subseteq A \implies g^{-1}Ag \subseteq A$$ holds. As you already said, this argument is valid if $A$ is finite, so $A$ cannot be finite.
Think of the elements in $G$ as moves, of $A$ as a property and of elements of $A$ as moves with that property. So we need a property of moves that is preserved when first moving in one way beforehand and then moving in the opposite way afterwards, but that is not preserved the other way around - when first moving in the opposite way beforehand and then moving in the original way afterwards.
The simplest infinite set would be $\Bbb Z$, the simplest moves on $\Bbb Z$ would be jumps to the left or to the right, but more generally any permutations of $\Bbb Z$. And the simplest “ways” to move would be, well, left and right. The simplest property of a move would be fixing stuff.
So the question becomes:
Well, if a move fixes some left half of $\Bbb Z$, it certainly also does so when moving even further left before and moving back right after – but when I move right first, there’s no guarantee anymore!
So, that’s how you could come up with the counterexample . . .
Note that the way $A$ is defined in the text is a bit convoluted. A simpler definition might be $$A = \{f \in G;~f(n) = n\quad\forall n \le 0\}.$$