Cut the female first. Sand the sides until perfect then measure, mark out and cut the male part. I cut the male part 1-2mm wider to leave room to make the fit.
If you accidentally make the male part too small when fitting cut a bit off the tip.
The male part should be 0.5mm wider when finished so that the parts naturally hold together.
There should be no light showing through the joint when fitted.
If you don't manage to do such a great job then 15 mins of steaming the joint then clamping until cool solves most issues!
Also there is no need to add a wood underlay to the joint. They don't need any support back or belly.
Using hide glue is a good idea too