I got my current 4 day gig just by being upfront with everyone I interviewed with that that's what I was looking for, and waiting until someone said yes.
However, when it eventually came to negotiating after successfully interviewing it was still difficult and I had at least a few companies - to my huge frustration - try to push me into a full time role or even tell me they weren't setup to handle my request yet but would be in future! With the role I eventually accepted I still had to work full-time during my probation period before I could reduce my hours due to limitations with their processes (apparently.)
To help answer the originl question, at my former employer - The Financial Times - a 4 day week was fairly common amongst folks with young children.