A weak acid (tomato paste, dilute vinegar, ...) will help with burned-on stuff, but the real trick is just good, hard scrubbing with an abrasive (steel wool or similar).