Most secure way to generate a random session ID for a cookie?
If the only information in the cookie is an identifier, essentially a label, the only attack you're trying to protect from is an attacker guessing what it is.  So use some random bytes.  Enough random bytes that it's "unguessable."
Then squish the random bytes into something that fits within the confines of which characters you can use in a HTTP cookie.  base64 works for this.  It's not absolutely optimal, because there are more than 64 cookie-safe characters and it tends to leave trailing == characters which add bytes to the header but not randomness, but that's fine.  It works and Python can probably do the base64 encoding faster than anything else we can come up with.
If you also want to prepend the user ID to it, that will make things easier to trace and debug, which will probably make your life easier, so go ahead.  It doesn't give an attacker any significant advantage.  (unless they manage to steal one without being able to otherwise determine what user they're stealing from, which seems unlikely.)
I'm writing my own sessions controller that issues a unique id to a user once logged in, and then verifies and authenticates that unique id at every page load.  What is the most secure way to generate such an id?  Should the unique id be completely random?  Is there any downside to including the user id as part of the unique id?