There are many uses for the word 'get' and one such instance is following it with a "participle" like 'started'
Anyway, I think "I get started on the new story" as well as "begin a new story" may sound a bit vague, at least to me as it can go two ways - either you starting to write a story or read one... If you are referring to the former case than perhaps you can say " I have to get started on writing this story"
It's not passive. "You'll get punished" (= "You'll be punished") is passive, because you'll be punished by someone. But if you "get started", you won't be started by anyone.
In expressions such as "get started", "get" has the sense of "reach a state of being ...", or "become". It's the same sense as when someone "gets bored" or "gets drunk"; (though if you say "That beer will get drunk", then it is passive).
Sometimes it's a very fine line between the two constructions: "He's getting bored" is arguably not passive if it just refers to the state of boredom, not caused by any particular 'agent'; but "He's getting bored by the story" is clearly passive: the story is boring him.