We are also allowed to work for up to 120 days here before we receive our license. (In N.H., we're "licensed" instead of certified.) The BON doesn't mail our licenses anymore, though, so I had to keep checking on their website. It took me about 2 weeks from the time I sent it in to get licensed. Even though N.H. says that you have up to 120 days, I found that everytime I applied somewhere, they wanted me to be licensed/certified. It was kind of a pain, but now I finally have a job, so it's okay.
I would say it took about 3 weeks for me to get a job after taking my state test. Oh, and I know how much it sucks trying to find the shift you want. I always saw openings for 2nd shift (3-11 or 2-10) when I was job searching, because no one ever wants to work that shift. I lucked out and got 7-3, which was my first choice.
Good luck on your job search