Well, if it were specifically for the Sony reader then the native LRF format can do much of what you want, and if you convert from HTML source it will work fine (you can turn HTML into LRF easily using
Calibre). Plus you can move the HTML to other formats quite easily.
I have been experimenting with "choose your own adventure" setups
like here but the main issue is that for any but the simplest story forking the amount of "text doubling" (where you have to write the same pages from the viewpoint of action A and from the viewpoint of action B until the fork resolves) grows exponentially. I'm not too good at explaining this but follow the link and look at the HTML source to see. There are some inherent limitations to doing things this way.
The way to solve this would be by using a preprocessor of some sort which will help you automatically write/sort out these "forks" in stories or, harder but vastly more interesting, by porting a dedicated javascript z-machine engine such as
Parchment which you can see
in action here. We already know it is possible to run custom javascript as shown in the games
here but I don't know how extensive this javascript support is nor how easy it would be to port this game engine. And of course you'd have to sort out an input method, discussed
here.
PDF is ultimately quite a poor format choice for this venture, I think.