I will be printing it in a local print shop so should I first find out what kind of paper I’ll be printing on and then edit the photos and book in its ICC profile? Or first get the design down?

The printing and the design are unrelated. You could design the book with unedited photos if you wanted or you could design it with fully edited and proofed photos. It doesn’t matter.

I edit photos normally on my computer screen. When it comes time to print the photos, I get the ICC profile from my print lab for the specific type of paper I am going to use. I create a duplicate copy of the picture, then then soft proof my edited picture using the ICC profile. I edit the duplicate picture while in soft proof mode so it matches the original. For me, I find that increasing brightness until it is similar to the original then adding contrast is sufficient. Additional saturation may or may not be needed.

Best advice would be to contact the printers and follow their recomendations. Different printers have different level of understanding colour management and different approaches to it. In general best way is to keep things simple - no fancy profiles of colour spaces, just default industry standart ones. Printers will apply what’s needed on their side.