Oracle Construction for Grover's Algorithm
The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.

For example, suppose you have a 3-sat problem:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)


Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x


Now make a circuit that computes whether the input is a solution, like this:



Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):



That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.

Iterate diffusion steps with oracle steps, and you've got yourself a grover search:



... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).