@hallnotaryservices, I'm in the same boat too! I think a lot of it comes down to marketing and luck. We may be able to fill in when other notaries can't make signings.
However, if another forum member could chime in about companies that hire newbies, that'd be helpful. I'm assuming that most companies would prefer more experienced notaries, but everyone's got to start somewhere.