Quote by jwr:
"Where do you start to look for this and is it weird to have it on a brand new bike?"
The dealership.
Or the Zertz! J/K
It could be the pedals are not threaded tightly enough into the crank arms or greased threads in the crank arms. Remove, lubricate and re-install to torque spec.
It could be the crank arms at the spindle. Remove, lubricate, re-torque. Check for end play.
It could be the bottom bracket, itself. Some of the newer PF types are prone to the bearings generating noise in the BB shell.
It could be the stem/handlebar joint creaking to your pedal stroke. Remove, use a light film of silicone grease and re-install to torque spec.
It could be the brake/shifter mounting bands sqeaking on the bars. Check torque of mounting bolts.
It could be loose chainring bolts. Remove, grease and install to torque spec.
It could be the saddle rails creaking to your pedal stroke in the seatpost clamp or where they enter the saddle. Re-torque saddle clamp and flow light oil into rail/saddle interfaces.
It could be your shoes or cleats squeaking. Check torque and lubricate bolt plate. Install skateboard grip tape between cleats and shoe soles.
Those are a few areas to look. There are others, of course. Some of the above are specific to the drive train. Some 'sound' like they are timed to the drive train via the pedal stroke.
Noises are sometime easy to track and eliminate. More often than not a couple-three attempts are required to find the root cause. Noises are best diagnosed with a friend pedaling the bike while you walk along side and listen for where the noise is coming from.