But how to know "męża" if husband is "mąż" ?
It's understandable that you don't know that at first, so this is the moment when you learn it. ą can often change into ę in different cases.
This is the genitive, correct?
Yes, "szukać" takes Genitive.
So, just to confirm, the geneitive singular for Mąz is Męża?
why not szuka na męza.?
Because English has phrasal verbs, and usually each one of those "look for" "look after" often translate to different unique verbs in Polish.
So look for= search=szukać
Still to this day, it's very useful to read