Whats your attic insulation situation? If its bad, I would address this first. You lose most of your heat through your attic, something like 85%. I would ensure that it's air sealed and properly insulated. Then I would address any gaps around windows, doors, and other penetrations. Then, if you feel it necessary, address the walls.