Hopefully this will save someone else a few steps when they hit the same problem.
We had a thunderstorm a few weeks back, and the power blipped. Stuff came back on but some of it - including the printer - wasn't quite the same afterwards. In particular, the printer was very erratic about whether it would show up in AirPrint or not.
Mostly not, to be honest.
After trying the usual steps (power-cycle the printer, the router, the device I'm trying to print from...) I tried turning AirPrint on and off on the printer itself. That seems to have worked.
There are a few steps involved, but they should be fairly straightfoward taken one by one, so I thought I'd lay them out.
Find the printer's network address
We're going to talk directly to the printer using a web browser. To do that we need to know it's address. Network addresses are a bunch of numbers.
The HP website has a page explaining how to get a configuration report from the printer. Look for the section "TCP/IP(v4)", and that will include the network address, if the printer is on your network. (If it isn't on your network this post won't help you!)
Visit the printer webpage
Once you've found the address open your browser and type http://the-address/ in the address bar. For the sake of example we'll use 22.214.171.124, so we'd be visiting http://126.96.36.199/
You should then be looking at a webpage belonging to the printer. It should say "HP LaserJet M15w" (or whatever model you have) in the top left, and you'll probably be looking at "device status".
Click on the "networking" tab, and then click on the "advanced" link, as in the image below.
Turn off AirPrint
In the advanced section there are a ton of little checkboxes saying which services are turned on or off. There are three we need to turn off - IPP, Bonjour, and AirPrint.
Go ahead and clear those. When you've done that, click "apply" down in the bottom right.
Turn back on AirPrint
After clicking apply, go back and turn those boxes back on, then click apply again.
At this point I found that my various devices could suddenly see the printer again. Hopefully you'll find the same thing.