It sounds like you've already correlated the clicking to pedaling, but just to be sure, correlate with one of the following items:
- Wheel rotation: does the clicking stop when you stop pedaling (which also stops most drive train parts moving). If it continues, it may be a wheel hub or freewheel problem. See bike shop1.
- Specific gears: If the frequency of clicking changes as you change through gears when you pedal, it could be chain, derailleur, or cassette. See bike shop1.
- Seat rocking: While coasting, without pedaling, try rocking left to right a small amount, bouncing up and down on your seat a little, or making a pedaling motion with your feet off the pedals. If you hear the clicking, it could be a loose seat or just seat fabric rubbing against metal or plastic parts as you pedal.
- Pedaling: If it only occurs when you're pedaling and the number of clicks is constant with pedaling (doesn't change as you change gears), then it's most likely dry pedal axel threads, or less likely pedal spindle bearings or bottom bracket.
- Bonus, if the volume of clicks varies with how hard you're pedaling, that's another indication that this is the case.
IMO, the most likely is #4, specifically dry pedal threads. Luckily this is easy to test as follows:
Have a look at your pedals. They will be removable from the crank-arm either with a flat pedal wrench around the collar of the spindle, or a large allen key through the back:
Image from Park Tool article which provides more detail.
Remove them, clean the threads, and apply a small amount of grease to the threads, then put them back in and tighten them up nice & tight. Note that the drive-side pedal (right hand) will be threaded "normally" and the left side pedal will be reverse threaded. If the clicking goes away that was it.
I find both my bikes start doing this after 2-3,000km of riding, but if the shop didn't grease the spindles or under-greased them this could start earlier.
If that's not it, then it could be the bottom bracket, in which case I would advise you have the shop work on it unless you're pretty comfortable dismantling the drivetrain of your bike.
1 "See bike shop" recommendations are not based on an assumption about your bike repair skill level. They are because your bike is new and should not have major items like wheel hubs making weird noises.