Definition
A decision procedure is an algorithm that, given any input from some domain, halts in finite time with a correct yes/no answer to a fixed question. "Is n prime?" has a decision procedure (trial division). "Does this program halt?" does not (Turing's halting problem). A set is recursive if and only if its membership question has a decision procedure.
Why it matters
How it works
To establish that a problem has a decision procedure, exhibit the algorithm: explain how, given any input, it determines the answer and halts. To establish that a problem has no decision procedure, reduce a known undecidable problem (often halting) to it: show that if you had a decider for your problem, you could solve halting. The reduction proves the problem is at least as hard as halting and therefore undecidable.