I would get in the habit of practicing talking about your experiences and your projects and your passions on a regular basis -- not just while job searching! Being able to speak confidently about yourself and your accomplishments will get you far in a lot of different ways, like presentations, generic social engagements, and even dating. But perhaps more importantly, it's a great way to sell yourself
within your company. At 1:1s with your (new) boss, practice talking about your projects. Your goal is to sell yourself, to make your boss think you're all that and a bag of chips. (Hopefully, it's true!)
I know this doesn't help that much right now while you're looking for a job, but it really helps to practice all the time.
For a more practical solution: I go for a 30 minute walk every morning, and during that walk, I often talk aloud about whatever is on my mind. Very often, I'm practicing a pitch that I want to make to someone else, or a speech I want to give, or a witty, snarky comeback that I should have given when Bob insulted me in front of the cashier at Starbucks. I do it every day, and I've noticed that in my "real" life, I stutter less and I come across as more persuasive than I did years ago before I started doing this.
So to answer your last question: every day for at least 10-30 minutes :)