All sound advice above: either hot hide glue, or the cold alternatives (titebond or even white wood glue). All of these suggestions require some cleaning, clamping, or weight on top for at least a few hours, preferably a night and day. Hey, there's a song in there! Both ways make very strong connections - after all, it's what good furniture makers use. Hide glue smells nasty, doesn't fill any gaps (so you have to ensure a perfect fit) and requires some limited dexterity (mix, heat, stir, apply quickly, clamp, clean the residue), but it's completely reversible (hot water does the trick). For making a small amount, a glass of hot water or a micro-wave will do. And a small bag of glue pellets or chrystals goes a very long way.
But what I wanted to add: by NO means use superglue or instant glue. Cyano-acrylate as it's officially called, stains wood and gets sucked into it, it's so liquid it doesn't fill any gaps - so very little bonding strength - and even worse, it's impossible to remove without sanding and carving.