First thing is to make sure you pick a plot you know you'll enjoy writing out. CYOAs can be a lot of work, usually more than people just starting out expect, and so you need a topic that will keep you interested the whole way.
Seconding what Killa said about starting small, you'll be surprised at how much even a simple scenario can branch out. A lot of people seem to plan these big yet vague epics like leading an army of a kingdom at war and whatnot, or go into exhaustive detail on their settings without really considering how they'll handle actually getting the characters from point to point while including choices on the way. Meanwhile there are a thousand smaller, more personal stories that are probably more interesting too that could be told using those kinds of scenarios just as a backdrop.
Remember too that you're not in any rush. Keep the quality consistent, polish and proofread, check in here for feedback every now and then, and basically just try to make your first story a complete one you can be proud of.
