Agree... working 4 days can be quite nice. Make sure you agree a Gross Salary, so that should the nanny decide to work other days, it won't make a big difference to you.
Start your search now, indiciating clearly the intended start date. As time goes on, increase your marekting efforts if you haven't got sufficient interest. Start off with low cost advertising, locally and on the web.