Can a non-finitely generated semigroup be a subsemigroup of a finitely generated one? Sorry! The answer doesn't seem obvious at all to me...
If $\langle S \rangle \leqslant \langle T \rangle$ can $S$ be infinite while $T$ finite?  I think the answer is yes.
Let $\Bbb{Z}^{\times} \supset T = \{p\}$.  Then choose $p^2, p^3, p^5, p^7, \dots, p^{\text{prime}}$ for $S$.
 A: Your counter example seems good to me. Edit (following @bof) : actually it is not that good. If we have $H=\langle p^q\mid q\text{ is prime} \rangle$ then $H=\langle p^2,p^3\rangle$. The reason is the following, clearly $H$ will contain it. Furthermore, $p^2,p^3,p^4,p^5$ are in $H$. And if $n\geq 6$ at least one $p^n$ or $p^{n-2}$ or $p^{n-4}$ will be something like $p^{3k}$ so that any element in $H$ will be contained in $\langle p^2,p^3\rangle$.
Remark that such counter-example also exist for groups. 
The classical counter-example is $\mathbb{F}_2=\langle a,b\rangle$ with two generators and its derived subgroup $D(\mathbb{F}_2)$, it can be shown that $D(\mathbb{F}_2)$ is not finitely generated (it can be shown that this is the fundamental group of an infinite grid). 
A: Another example. The subsemigroup of the free monoid $\{a,b\}^*$ generated by the set $a^*b = \{a^nb \mid n \geqslant 0\}$.
A: It is true that a finitely generated semigroup can have a non-finitely generated subsemigroup, but I don't understand your example. Isn't $\langle p^2,p^3\rangle=\{p^n:n\ge2\}$?
In fact, every countable semigroup can be embedded in a $2$-generated semigroup. This was shown by Trevor Evans, "Embedding theorems for multiplicative systems and projective geometries", Proc. Amer. Math. Soc. 3 (1952), 614-620.
In view of the fact that every semigroup is isomorphic to a semigroup of mappings, Evans' result was implicit in an older result about mappings, namely, that every countable set of selfmaps of an infinite set $E$ is contained in a semigroup generated by two selfmaps of $E.$ This was first proved by W. Sierpiński, "Sur les suites infinies de fonctions définies dans les ensembles quelconques", Fund. Math. 24 (1935), 209-212. A simpler proof was given by Stefan Banach, "Sur un théorème de M. Sierpiński", Fund. Math. 25 (1935), 5-6. See also the solution of Problem 6444 in Amer. Math. Monthly 87 (1980), 676-678.
There are analogous results for groups: Graham Higman, B. H. Neumann, and Hanna Neumann, "Embedding theorems for groups", J. London Math. Soc. 24 (1949), 247-254; B. H. Neumann and Hanna Neumann, "Embedding theorems for groups", J. London Math. Soc. 34 (1959), 465-479; F. Levin, "Factor groups of the modular group", J. London Math. Soc. 43 (1968), 195-203.
Note that any example of a finitely generated group with a non-finitely generated subgroup is also, if we forget about inverses, an example of a finitely generated semigroup with a non-finitely generated subsemigroup.
