Why is my new apple watch unable to connect with my iPhone? It says that I need to update my watch, then says update failed because my watch isn't connected to an internet connection.

See this;

If you see 'Unable to Verify Update' when updating Apple Watch - Apple Support

Try

First force restarting your iPhone by whatever method your version calls for.  As soon as you see the Apple logo force restart your watch by holding in the crown and side button for 10 seconds till you see the Apple logo then release.  Log into your iPhone and wait for your watch to boot, then log into it.

Failing that, I'd try resetting your network settings.

From your iPhone>Settings>General>Reset>Reset Network Settings

You will need to log back into any WiFi networks you use.

Also reset your router by unplugging it for a full 2 minutes and then plug it back in.

Also you can try the following

Step 1. Hard Reset Watch 3 (Hold down crown button and power button until screen goes black. When apple logo comes on take your finger off crown button and hold power button until you see the watch prompting to erase all data) Erase all Data

Step 2. Delete watch app on iPhone and then download it again on iPhone.

Step 3. Make sure you are connected to 2.4 Ghz and not to 5 GHz

Step 4. Make sure that you that you bring phone and watch closer to wifi router/modem.

Step 5. Put watch on charger

Step 6. Put phone on charger

Step 7. Put Your phone on airplane mode but have Bluetooth and WiFi turned on.

Let us know if either one of these 3 fixes work.