The design of a set of beamformers for the multiuser multiple-input single-output (MISO) downlink that provides the receivers with prespecified levels of quality-of-service (QoS) can be quite challenging when the channel state information is not perfectly known at the base station. The constraint of having the SINR meet or exceed a given threshold with high probability is intractable in general, which results in problems that are fundamentally hard to solve. In this paper, we will develop a high quality approximation of the SINR outage constraint that, along with a semidefinite relaxation, enables us to formulate the beamformer design problem as a convex optimization problem that can be efficiently solved. For systems in which the uncertainty size is small, a further approximation yields algorithms based on iterative evaluations of closed-form expressions that have substantially lower computational cost. Since finding the beamforming directions incurs most of the computational load of these algorithms, analogous power loading algorithms for predefined beamforming directions are developed and their performance is shown to be close to optimal. When the system contains a large number of antennas, the proposed power loading can be obtained at a computational cost that grows only linearly in the number of antennas. The proposed power loading algorithm provides an explicit relationship between the outage probability required and the power consumed, which allows us to precisely control the power consumption, and automatically identifies users who are consuming most of the power resources. The flexibility of the proposed approach is illustrated by developing a power loading technique that minimizes an average notion of outage.