Hmm, I've just come across a few patterns that might help--
this one from knitty.com explains how to attach handles, and if you look at their pattern archive and scroll down to the bottom section for bags, they have some examples of ones with and without linings. So that's not really a source for answers to your questions, but you can use different patterns as examples, I suppose!
I know what you mean about wanting to sew--I bought fabric to line a felted purse I just made, and I am sooooo bad at it. I'm not sure it's even necessary, but I thought it would add support. Who knows if I'll get that finished... :(