Connect C4580 to wireless network

[lord_vader]

I moved to a new house.  At my old house, my HP Photosmart C4580 had a wireless connection to my wireless router and my Apple Mac desktop computer.  Now I'm at my new  house, have the same printer and Mac desktop but a new wireless router.  I know the router network name and password.  How do I connect the printer to the new router?  Have spent close to 2 hours searching HP support forums and on Google but nothing seems to have worked so far!

[sabretooth04]

Replacing/changing your wireless router, try here.  

http://www8.hp.com/us/en/campaigns/wireless-printing-center/reconfiguring-system-help3.html

* Reset your printer back to Network Defaults.  Then run the Wireless Setup Wizard to connect.  Both can be accessed from the front panel or computer.  If no front panel for configuration, you must use your Printer USB cable to connect.  You can also try the WPS method if your router/printer supports this only if the Wizard or Printer USB cable is not available.  Read your User Guide for info.
* Set router to a fixed wireless channel like 1, 6 or 11, never ‘auto’.  Try channel 1 first then the others one at a time.  
* Make sure printer and router are at least 5 feet apart.  
* The router must have the 2.4G SSID band enabled with a different name than your 5.0G SSID band in your router.  
* Make sure IPv6 is disabled in the printer.

Make and model of modem and router?

However if you have a Gateway (modem+router) device, all Gateway devices are terrible for wireless connectivity.   If this does not work, suggest you think about putting that gateway device in full bridge mode and install your own high quality router that YOU have full control over.