First of all: Welcome!
Second of all: I'll assume you know nothing at all, so I apologise in advance if it seems a bit... overbearing.
Anyway, step one: Go into a region. That's a square on the map, by the way.
Step two: Find an overland chunk (i.e. one "room", for lack of better explanation) that is coloured differently in the map. Dark green are normal, bright green have entrances to the underground.
Step three: Go there and enter the underground.
Step four: Find bright yellow rooms. They're normally guarded by bosses, but sometimes you'll get lucky and there's one unguarded.
Step five: Destroy the gem deposits there and collect the gems. Success!
Oh, and in case you haven't figured that out yet, different chunks have different gems. Open up the big honkin' encyclopedia and look the gem up in the material compendium to see where to look.
