My new HP printer is connected to wifi but my Mac Air cannot find the printer. The message is "Printer is not connected".

Connect an AirPrint printer to a Wi-Fi network - Apple Support and then add it as an AirPrint printer. You must specifically select AirPrint.

Use AirPrint on your Mac - Apple Support

Print wirelessly from your Mac to an AirPrint printer

If your HP printer is not AirPrint-enabled, return it. It won't work.

On the Printer there should be a way you can view/print the printer's network settings. Open System Preferences-->Printers & Scanners. Add a new printer, click on the IP icon and use the IP address from your printer's network settings to manually connect to the printer.