We present a general method to construct a universal set of quantum gates using probabilistic teleportation as a basic primitive. The technique generalizes the teleportation method of gate construction to partially entangled quantum channels. Without recourse to local filtering or entanglement concentration, using local rotation and CNOT operations followed by measurements in the computational basis, one can construct many encoded quantum operations with unit fidelity but less than unit probability. The technique can also be applied to the construction of remote quantum gates that cannot be directly performed.