We introduce an approach to quantum information processing where the information is stored in the motional degrees of freedom of nanomechanical devices. The qubits of our approach are formed by the two lowest energy levels of mechanical resonators, which are tuned to be strongly anharmonic by suitable electrostatic fields. Single qubit rotations are conducted by radio-frequency voltage pulses that are applied to individual resonators. Two-qubit entangling gates in turn are implemented via a coupling of two qubits to a common optical resonance of a high finesse cavity. We find that gate fidelities exceeding 99% can be achieved for realistic experimental parameters.