Do I need to create a new world to get things like strongholds, towns, and mine shafts? Or does it randomly generate on my existing worlds after I updated the game?
With every other world generation update, it generated the new stuff with newly made chunks. So if you have explored a huge section of the world, it won't change. But go beyond, and you'll get the new stuff.
So go for a walk :)
Time to add a new pipe on the Great Nether Subway... I think we'll pop out somewhere far south.