I found both my first socketed item and my first gem in Act II after I
killed Magdha.
However, both @Sterno and @OrigamiRobot found gems before the activity above - so far, it seems Act II is the only real concrete limitation so far.
However, both OrigamiRobot and @Resorath confirm a similar experience (a gem dropping off the activity above). It seems that a gem will always drop from said mob. It does not seem a socketed item drop is guaranteed, though.
It's a few more quests until you find the Jewelry Artisan, Covetous Shen, but it is shortly thereafter in the same Act. You can find gems before him, and before the activity above.