Find a stuffed animal. I found this bear at Goodwill for less than a dollar.
(It had an ugly plaid bow tied on it, which I promptly ripped off of it. Now it looks better ^_^)
Eww. Wash the stuffed animal.
(Unclean plushies are gross. Just throw it in the washing machine with some other laundry.)
DO NOT PUT IT IN THE DRYER!!!
Stuffing is made of plastic fibers, so if you heat your animal, it will burn up and melt and be ruined. No one wants that.
Allow your plushie to air dry for a little while.
Carefully cut open your bear (or other animal) along the back seam. You should be able to pull the seam apart a little and find the thread holding it together. Just cut the little string and start working the seam apart.
Next, rip the innards of your poor little animal right out!
It may be a little wet from the washer, but no big deal. (It just feels gross.)
Next, check and see if your animal's limbs are open to the body. If they are (like mine) I suggest that you sew them up to prevent stuffing from coming out of the arms and legs since the belly is now empty.
Cut circles from scrap fabric to cover the holes.
Sew them in place.
Yay. One down. Continue for all leg/arm holes.
Make sure the head has enough stuffing, and then cut a larger circle and sew the neck up as well.
Now, you need to make a lining for your bag.
This is tricky, and you mostly have to guess to get the shape right.
I started out by folding a piece of fabric (about 10 by 18 inches) in half (making it 10 by 9 inches) and then sewing along the short edges, leaving one side folded and the other open.
Then, I tried it out in my bear, and decided to make the edges rounder, so I sewed the corners of the rectangle and cut off the extra fabric.
Remember to leave an opening that matches the size of your bear/animal's seam.
Now for the tricky part - attaching the lining correctly.
Place the lining in the bear, so that when you look it, you see the good seam.
Then, fold one side of the liner and the bear's seam inward and pinch them together like you want them on the finished bag.
Holding that part together, pull the liner out and turn it inside out, so that the good seam is on the outside.
Now, starting where you have the fabric pinched together, place pins to hold the liner in.
Work down one side like that, then sew it.
(This is very confusing, I know. I sewed the liner in right-side-out the first time by accident. If there's a way that works for you, just do it. It's hard to explain.)
Now, to sew the other side.
It's difficult to get to, because the bear's in the way. Unlike a bag, which you can just stuff into the liner inside out to sew, the bear has a stuffed head and limbs to worry about.
Mostly, just do whatever you can to get the other side to match up so you can sew PART OF IT. (You still need to turn the bear right-side-out again, so leave room.)
I stuffed the arms and legs of my bear backwards into the stomach, and left the head out.
Turn the bear/lining right-side-out again, and tuck the lining inside.
If all went well, you see the good seam and your lining is almost completely secured to the bear.
Now, it's time to neatly slip-stitch the rest of the way up the lining.
Ta dah. The lining is finished.