For needle turn applique, press the freezer paper to the RIGHT side of the fabric and trace around the shape. Then remove the paper from the front and applique the piece to the background using your marked lines. This way there's no need to remove the paper later and no cutting anything away.
I generally only cut away material if the top layer is a lighter fabric and the bottom layer fabric is showing through. You can also cut it away if there are a lot of layers and you'll be hand quilting it. Otherwise I just leave it alone.