Well, it's basically the same way you procedurally generate any map, and the way to accomplish it is very dependent on your game. For instance, what obstacles are there? How many paths are you looking to generate? Do the paths have to follow a general outline (i.e. League's "3 lane" style)? What are the points of interest on the map? How do you want them to be arranged? What's the maximal/minimal distance between things? Etc, etc...
The basic idea of proc gen is to come up with a series of rules and have an algorithm follow those rules within randomised parameters. These rules can be "ground up" with the computer following basic rules to generate complexity or "top down" where you have specific rules and the computer is restricted in it's generation to following those rules strongly. You'll be almost guaranteed to need a pathfinding algorithm.
Proc gen requires a relatively thorough knowledge of coding (compared to creating say, a platformer), because you'll be running into quite complex interactions between things and you have to have a pretty thorough understanding of how things
should work so that you can pinpoint where you are going wrong when things don't work. It takes a lot of effort and research, but it's also quite fun if you enjoy that sort of thing.
Here's a link dump to get you started. It's not all specifically related to exactly what you're asking (though some is), but it has a lot of general info that helps to understand the process of proc gen:
blog.jrheard.com
en.wikipedia.org
pcg.wikidot.com
wiki.secretgeek.net
(This article series has nine parts: parts one , two , three , four , five , six , seven , eight and nine ). Back in 1992 (or perhaps 1993...
roguelikedeveloper.blogspot.com